ABSTRACT

The topology control is an effective approach which can improve the quality of wireless sensor network at all sides. Through studying the mechanism of sensor network data transmission, the nature of data transmission in wireless sensor network is concluded as a kind of responsibility transmission. By redefining the responsibility and availability of nodes, the strategy for cluster head selection is studied, the responsibility and availability is determined by the combination of the residual energy, location and current flow of nodes. Based on the above, new clustering network topology control algorithm based on responsibility transmission CNTCABRT and hierarchical multi-hop CNTCABRT is presented in this paper, whose algorithm structure is along the famous LEACH algorithm. Experimental result demonstrates its promising performance over the famous LEACH algorithm in the cluster head selection, the size of cluster, the deployment of nodes and the lifetime of nodes, and several innovative conclusions are proposed finally.

1. Introduction

Wireless sensor networking had become the most challenging topic in the IT field at present. Network topology architecture control is not only the premise and basis for studying high-efficiency node deployment and routing protocol design, but also the basic assurance to comprehensively save node energy and improve network performance [1-4]. Therefore, studies of the topology architecture control strategy and algorithm with low energy consumption, low network delay, and high reliability serve as the groundwork for wireless sensor networking.

Based on an analysis of the operation mechanism, advantages, and disadvantages of the LEACH algorithm [4-6] and its strategy for cluster head selection, we proposed the Clustering Network Topology Control Algorithm Based on Responsibility Transmission (CNTCABRT) in this study. The proposed algorithm considers many network factors, such as the distance between node and cluster head, residual energy of node, and data traffic of nodes, during cluster head selection, thus overcoming the shortages of the LEACH algorithm. Performances of the CNTCABRT algorithm were investigated in terms of deployment of cluster head, quality of cluster head, size of cluster, energy consumption of node, lifetime of nodes. This study increases the family members of network topology control algorithm based on cluster.

2. Related Work

The most representative topology control method based on clustering is the famous LEACH algorithm, which is a self-adaption clustering control algorithm implemented through iteration [5]. Every round of iteration is divided into two phases: establishment of clustering and data communication. First, adjacent nodes dynamically form a cluster and a cluster head is determined randomly. The nodes within the cluster will send data to the cluster head, which then transmits the data and results to the sinking node. The cluster head mainly functions for data fusion and communication to the sinking node, resulting in large energy consumption. During self-organization, the LEACH algorithm randomly selects the cluster head and avoids excessive energy consumption of cluster head node, which, thus balancing network energy load to a certain extent, reducing energy consumption during communication, and effectively prolonging the lifetime of the network [6]. However, the LEACH algorithm does not consider residual energy and the location of nodes when selecting the cluster head, thereby easily causing uneven distribution of cluster heads, uneven node energy consumption, and unreasonable topology structure. Studies have shown that the LEACH-centralized algorithm [2] offsets the shortages associated with random cluster head selection and insufficient consideration of the amount and location of cluster heads with every round of iteration, thus improving the quality of produced clusters. However, meaningless energy consumption, and consequently cluster expenditure, is increased by the periodical reporting of energy, location, and other information of each node to the base station and the transmission of unrelated information. A previous study used Data Aggregation-Exact and Approximate [3] first clustering for cluster head selection of the whole network, after which the pool of cluster heads was used for determining secondlevel cluster heads. Data was transmitted to the base station through the second-level cluster head. This algorithm is difficult to implement and increases time delay of data transmission among nodes.

3. Methodology

In general, the CNTCABRT algorithm follows the same clustering principle as the LEACH algorithm. Studies on the mechanism of wireless sensor network data transmission have revealed that sensor network data transmission improves with responsibility transmission. Thus, we proposed an algorithm that selects the cluster head through the strategy of accumulating evidence with responsibility. Briefly, the algorithm periodically divides the whole sensor network into several clusters, with each cycle referred to as a round. Each round involves cluster formation and data transmission. The algorithm exhibited good performance in controlling cluster head selection, cluster deployment, and cluster size.

3.1. New Understanding of the Mechanism of Sensor Network Data Transmission

From the data perspective, information is generally concealed by abundant multi-sensor source data in the wireless sensor network. There is a certain “cause-and-effect” relationship between information and multi-sensor source data reflected by the “transmission” during information flow, such as data transmission from common nodes to boundary cluster head, data retransmission from boundary cluster head to base station, and so on. In this process, the self-adaptive selection of the boundary cluster head can be considered as the effect, since only those with strong availability can be selected as the boundary cluster head. Here, it is possible to regard such “availability” as the responsibility of nodes to the network. Based on this idea, data transmission in a sensor network can be understood as a growth process of “responsibility” expressed by the continuous selection of cluster head by nodes. This process can be compared likened to a data structure tree, where nodes with poor responsibility and availability during the growth process are eliminated, leading to the untimely end of cluster heads and nodes that were not selected for data forwarding. Therefore, the nature of data transmission in a sensor network is a kind of “responsibility transmission”, where responsibility and availability are influenced by node energy, transmission delay, distances between nodes, and other factors in the sensor network.

3.2. Strategy for Cluster Head Selection

In this section, we study the strategy for cluster head selection based on the transmission mechanism above and the Affinity Propagation Clustering APC from literature [7]. We aimed to redefine the responsibility and availability of nodes that were transmitted with comprehendsive consideration of the residual energy of node, node distance, energy consumption based on transmission distance, energy consumption based on data quantity, and other network factors. The maximum sum of responsibility and availability was taken as the accumulated evidence of cluster head selection.

Suppose that all nodes form a set , where n is the total amount of nodes.

Definition 1. ar (i,j) represents the appropriate rate between node i and j, which indicate the degree of node j appropriate for the cluster head of node i.

(1)

where is the coordinate of node i; is the coordinate of node j; is the current residual energy of node j (energy consumption in the energy loss model is influenced by transmission distance); is the estimate value of node flow, which is a constant in the LEACH algorithm; is the reference degree equivalent to the mid-value of matrix formed by; and is the degree of attraction of node j to node i, that is, the probability of node j serves as the cluster head of node i.

Definition 2. Node can be taken as the responsibility (r) evidence and availability (a) evidence of the cluster head and are redefined as follows:

(2)

(3)

where is the responsibility between node i and k. If k is viewed as the potential cluster head node, then responsibility is transmitted from node i to node k and is equivalent to the accumulated evidence for node k to be the cluster head of node i. is the availability between node i and k transmitted from node k to node i, as the Equation (1). It reflects the accumulated evidence for node i to select node k as the cluster head. Thus, it measures whether k can finally become the true cluster head after several rounds of self-adaptation.

Formulas (2) and (3) iterate according to Formulas (4) and (5):

(4)

(5)

where is the learning rate in updating and.

Responsibility and availability transmit among nodes in actual network until all node energy is consumed. In addition, the value of continuously changes after each round of data transmission. A high value indicates stronger evidence and greater possibility for node k to become the cluster head; otherwise, node k cannot be selected as the cluster head. Therefore, for each round of circulation of the algorithm, select the k with the maximum value of. If, i is the cluster head; if, then k is the cluster head of i.

3.3. CNTCABRT Method

The CNTCABRT algorithm is an application of the wireless communication energy transmission loss model [8]. Energies consumed for transmitting every bit data to the preset distance is as the follow:

(6)

where L is the preset distance; and are energies consumed for sending and receiving data, respectively; and are the energy consumption of the signal amplifier; and is the critical distance between Friss free space propagation model and multipath attenuation model (). Shorter distance from all nodes within the cluster to the cluster head indicates lower energy consumption for communication within the cluster. According to the strategy of cluster head selection (Section 2.2), the probability that a node becomes selected as cluster head depends on three node characteristics: energy, flow, and transmission distance. Therefore, the algorithm will select a node with greater residual energy and less transmission flow as the cluster head. Our findings led to the construction of the following algorithm:

Algorithm 1: Basic CNTCABRT

Step 1. One hundred sensor nodes are produced randomly. The initial energy of the initial node is, the maximum circulation round is, and iterations of evidence updating is IterMax;

Step 2. While ()

Step 3. The appropriate rate is computed according to Equation (1). Set parameter P and learning rate and initialize and;

Step 4. While (current iterations)

Step 4.1. Update evidence matrix with Equations (2) and (3). Update matrix with Equations (4) and (5);

Step 4.2. Current iterations

Step 5. Obtain node k with for every node i. If, then i is the cluster head. If, then k is the cluster head of i. The network enters into a stable data transmission stage after successful cluster establishment.

Step 6. Current circulation round

The proposed algorithm may produce few nodes within the cluster, or even clusters with a single node. This problem can be corrected by combining these small or singular clusters with each other or with neighbor clusters.

Compared with the LEACH algorithm, the basic CNTCABRT algorithm utilizes the same time complexity but has increased time consumption for computing responsibility evidence. In addition, space complexity variation in the proposed algorithm mainly comes from the storage of accumulated evidence during cluster head selection. However, the strategy of cluster head selection follows the idea of overall optimization of APC algorithm. Therefore, the CNTCABRT algorithm can contribute to the optimization and control of network topology architecture. From this perspective, our proposed algorithm is better than the LEACH algorithm.

3.4. Hierarchical Multi-Hop CNTCABRT

The basic CNTCABRT algorithm utilizes single-hop communication between node and base station. If some cluster heads are far from the base station, they will consume more energy than other cluster heads during communication, thus possibly causing an untimely end for cluster heads under different environmental factors. Therefore, we studied the hierarchical multi-hop CNTCABRT method with the same energy loss model as the basic CNTCABRT algorithm.

Algorithm 2: Hierarchical Multi-Hop CNTCABRT

Step 1. One hundred sensor nodes were produced randomly. The initial energy of the initial node is, the maximum circulation round is, and iterations of evidence updating is IterMax;

Step 2. While ()

Step 3. The appropriate rate is computed according to Equation (1). Set parameter P and learning rate and initialize and;

Step 4. While)

Step 4.1. Update evidence matrix with Equations (2) and (3), and update matrix with Equations (4) and (5);

Step 4.2. Current iterations

Step 5.1. Obtain node k with for every node i. If, then i is the cluster head. If, then k is the cluster head. Forming the first layer of cluster head set: thusly;

Step 5.2. Compute for evidence matrix and of the boundary cluster head in set c using Equations (2) and (3) and Equations (4) and (5) respectively. Obtain k with and form the second layer of cluster head set:

Step 5.3. Enter stable data transmission stage, that is, node transmits data to the first layer of cluster head c and c retransmits data to boundary cluster head C, which retransmits data to the base station.

Step 6.

Obviously, the core idea of the hierarchical multi-hop CNTCABRT algorithm is to further form layers for the cluster head based on the basic CNTCABRT algorithm. This will enable optimization of the boundary cluster heads from the first layer of cluster head through data retransmission to the base station according to the strategy of cluster head selection (Section 3.2). The hierarchical multi-hop CNTCABRT algorithm is advantageous because it incorporates the advantages of the basic CNTCABRT algorithm and is appropriate for application in large-scale wireless sensor networks as well.

4. Simulation and Result Analysis

We performed a programming simulation under matlabR2009 environment in order to verify the efficiency of the basic and the hierarchical multi-hop CNTCABRT algorithms. Experimental parameters were set as follows: initial energy of sensor node; random deployment of 100 sensor nodes within the target regions of; the base station was located in the center of the region; set; data packet was 2000-bit long and control package was 32-bit long;,; energy consumption for data fusion was and data fusion rate was 0.6; the number of circulation rounds was 1000; and the probability for a node to become cluster head in the LEACH algorithm was 0.05. The reference degree p of the CNTCABRT algorithm was equivalent to the middle value of the matrix formed by. Learning rate was 0.9.

Comparisons of the basic CNTCABRT algorithm and the LEACH algorithm performance in clustering and cluster head selection are shown in Figures 1 and 2, respectively. In these figures, “o” represents common nodes, “*” represents the cluster head, a dotted line connects cluster head and nodes within the cluster, and a straight line connects cluster head and base station. Using the basic CNTCABRT algorithm for clustering, the selected cluster heads had a relatively reasonable distribution within a cluster of moderate size, since distances between nodes, residual energy, flow size, and other net-

work factors were taken into consideration during selection. In contrast, the LEACH algorithm exhibited a high degree of randomness in cluster head distribution and formed large clusters, thereby easily causing high energy consumption of local nodes.

We compared the energy consumption of basic CNTCABRT algorithm and LEACH algorithm (Figure 3). With greater number of iterations, the total energy consumption of both LEACH algorithm and basic CNTCABRT algorithm increased. However, the energy consumption of basic CNTCABRT algorithm decreased more slowly than that of the LEACH algorithm. The greater energy consumption in the LEACH algorithm can be attributed to uneven cluster head distribution, large cluster size, and abundant data for forwarding from cluster head. On the other hand, the basic CNTCABRT algorithm consumed well-distributed energy in the network due to the more optimized cluster head selection and deployment, which is beneficial for energy saving and slowing the rate of increase of energy consumption to a certain extent.

The comparison of basic CNTCABRT algorithm and LEACH algorithm in terms of node survival is shown in Figure 4. The basic CNTCABRT algorithm is able to

optimize cluster head deployment because it considers factors such as residual energy of nodes and distance between nodes in order to balance their energy consumption. Therefore, the first node of the basic CNTCABRT algorithm died later than that of the LEACH algorithm (at the 410th vs the 280th round, respectively). Furthermore, the last node death in the basic CNTCABRT algorithm occurred far later than that in the LEACH algorithm, indicating that the CNTCABRT algorithm is able to prolong network lifetime. The untimely end of nodes in the LEACH algorithm can be attributed to unreasonable cluster head deployment and uneven cluster size. In addition, with respect to the oversized clusters (Figure 2), cluster heads would have to retransmit abundant data groups, thus consuming relatively more energy and easily causing untimely end of nodes.

Figure 5 displays the results of clustering and cluster head selection using the hierarchical multi-hop CNTCABRT algorithm.

We compared the total energy consumption of the hierarchical multi-hop and basic CNTCABRT algorithms, as well as the LEACH algorithm (Figure 6). The basic CNTCABRT algorithm and LEACH algorithm apply single-hop communication for data transmission and their nodes consumed great amounts of energy due to the long distance between nodes. In contrast, the hierarchical multi-hop CNTCABRT algorithm applies multi-hops for data forwarding and applies the optimized strategy (Section 2.2) in selecting the second layer of cluster heads. Experimental results revealed that the hierarchical multihop CNTCABRT algorithm can save energy excellently and can slowly decrease the energy consumption curve.

A comparison of the three algorithms in terms of node death is shown in Figure 7. The first node death in the hierarchical multi-hop CNTCABRT algorithm occurred at the 465th round, thus significantly lagging behind the two other algorithms. Furthermore, the time interval between the first and the last node deaths was significantly

longer than that of the two other algorithms. Findings indicate that the hierarchical multi-hop CNTCABRT algorithm can save network energy while achieving good performance in prolonging node survival time. The death rate of nodes was slowed distinctively.

5. Conclusions

In this study, we investigated the mechanism of sensor network data forwarding and redefined the responsibility and availability appropriate for sensor network data transmission. In addition, we developed a strategy of cluster head selection that takes many network factors such as residual energy of node, data transmission distance, and flow into consideration in order to optimize the deployment and selection of cluster heads. We proposed the basic CNTCABRT algorithm and the hierarchical multi-hop CNTCABRT algorithm. Simulation results strongly proved the good performance of these algorithms. Further analyses led to the following innovative conclusions:

(1) The application of responsibility and availability to sensor network data transmission ensures the optimization of cluster head selection and optimization of network topology architecture control, thus performing double adjustment.

(2) The deployment and transition of cluster heads can increase the energy consumption of the network. Optimization of cluster head deployment can significantly reduce energy consumption and prolong network lifetime.

(3) Since cluster head deployment can influence energy consumption, clusters should be appropriately sized.

However, the basic and hierarchical multi-hop CNTCABRT algorithms take more time for clustering computation compared with the LEACH algorithm. Thus, future studies can further improve the proposed algorithms. Furthermore, possible application of the CNTCABRT algorithm in large-scale wireless sensor networks should be studied and a feasible routing protocol according to the topology control method of CNTCABRT should be studied.

6. Acknowledgements

This work is supported by the Fundamental Research Funds for the Central Universities (grant No. JUSRP- 211A41) and the National Science Foundation of China (grant No. 60704047).

REFERENCES