Keywords

1 Introduction

Wireless sensor network [2, 6], an infrastructure-less network, consists of a large number of sensor nodes deployed over a region of interest. The sensor nodes carry limited battery power, limited memory and slow processing speed. Sensor nodes sense the defined phenomenon and with the help of radio transceivers transmit the data to the base station (BS) for further processing. The base station or sink acts as an interface between users and network. All the nodes work together in-collaboration to accomplish the defined task, which a single node cannot be able to do. The battery power constraint sensor nodes work in an inaccessible region of interest where recharge or replacement of battery unit is quite difficult as well as costly. In the deployed region, nodes exhaust battery power in every point of processing, so energy-efficient processing by sensor nodes is necessarily needed to be addressed [13].

Clustering approach [1, 13] has been considered as energy-efficient approach for wireless sensor networks in which all nodes are grouped in independent clusters with one representative of each cluster termed as cluster head. Clustering algorithm provides the characteristics of energy efficiency, fault tolerance, scalability to the wireless sensor network. The much-needed energy efficiency has been achieved by aggregating the data of member nodes at cluster head and by avoiding the long distance communication, only cluster head node is communicated over long distance as the representative of cluster, TDMA schedule avoids the collision, idle listening and others related issues of MAC [3]. Literature [1, 3] suggests that clustering algorithm attains the load balancing in the network, but most of clustering algorithms assign an array of work to the cluster head to perform consequently, cluster head consumes much higher energy as compared to member nodes. The resulted load unbalancing deteriorates the performance of clustering algorithm.

Work of this paper proposed an m-way balanced tree data aggregation and communication scenario for intra-cluster communication in clustered WSN in which member nodes of a cluster are organized in an m-way balanced tree with cluster head node as root of the tree. In the proposed approach, node sends data to parent node, and data of all child node has been aggregated by parent node. Further, cluster heads will be active for less number of time slots in data communication phase of clustering algorithm. Consequently, the network is well load balanced. Rest of the paper is organized as follows: Section 2 demonstrates the proposed approach with working example. Section 3 shows cluster structure in proposed approach. Section 4 concludes the work of paper.

2 Proposed Solution

2.1 Problem Statement

Clustering algorithm provides the required cost-effective energy consumption of sensor nodes with add-on features of scalability and fault tolerance [1]. Role of cluster head is rotated among all the nodes to distribute the load and for well load-balanced network in clustering protocols [5, 8, 12]. The cluster head nodes are active for the entire clustering round, as an representative of cluster, only cluster head nodes communicate to long distance placed base station, and hence, the cluster head nodes consume much higher amount of energy as compared to member nodes [11]. Member nodes within a cluster disseminate different amount of energy because of their distance to cluster heads. As a result, the load balancing of network gets affected due to uneven energy consumption between cluster head nodes and member nodes. To solve the problem, [7, 10] provides the solution by constructing tree with cluster head as root and member nodes as the successor of root for intra-cluster communication. Member nodes rather sending the data to cluster head directly send the data to parent, parent sends the aggregated data to respective parent, and eventually, data has been received at the cluster head node. This multi-hop communication of data within the cluster reduces the energy consumption of cluster head node as compared to direct intra-cluster communication, but the tree formation is not structured, and the nodes in between the root and leaf do not have much data to aggregate. Therefore, there is a need of clustering solutions that can have structured tree formation for intra-cluster communication and to have better data aggregation for in between nodes to achieve a well load-balanced network.

2.2 Proposed M-Way Tree Data Aggregation Approach

In this paper, a distributed clustering approach has been proposed to do well load balancing in the network. For the network model, the proposed approach considers that (i) there are N number of sensor nodes are deployed over the square region and there is only one base station located outside the region of deployment, (ii) each sensor node knows respective location in the region by means of positioning algorithm [9] as the part of network set-up, (iii) nodes are stationary after deployment, and (iv) each node has been assigned unique local ID for identification.

Fig. 1
figure 1

Operation of proposed approach

Full size image

The operation of proposed approach has been shown in Fig. 1. Operation of proposed approach has been carried in rounds and each round has two phases (i) Set-up phase and (ii) Steady phase. In set-up phase, cluster formation is performed locally by the nodes, and the data transmission from member nodes to base station has been performed in steady phase with in-network data collection and aggregation by cluster head node. Set-up phase starts with the selection of cluster heads by means of probabilistic approach [8]. The selected cluster head nodes broadcast the status message to the network, and the nodes select the nearest cluster head node based on received signal strength (RSS) of broadcast message and replies to the preferred cluster head node with location information. Then, the proposed approach performs the m-way balanced tree set-up operation for intra-cluster communication. Each cluster head node knows about the location of all member nodes of respective cluster. Cluster head node constructs an m-way balanced tree (with predefined value of m) with self as root of the tree and member nodes as descendant. The characteristic of m-way balanced tree makes the cluster well load balanced as the distance of data prorogation is almost similar for each branch of tree. After the m-way tree set-up operation, cluster head node constitutes the TDMA schedule for respective cluster and broadcasts the TDMA schedule to the all member nodes.

Fig. 2
figure 2

Equal size clusters

Full size image

In the steady phase, data of the cluster has been collected at cluster head node. The parent node gathers data from the child nodes and aggregates the collected data with own data and forwards the locally aggregated data to respective parents. The nodes wake-up to send the data to parent with TDMA schedule, otherwise remains in sleep state. The proposed approach allows parents node to aggregate more data as compared to other tree-based approach and hence reduced the work of data aggregation over the cluster head node. The data has been eventually received by cluster head node. Cluster head node sends the data to base station. After completion of current round, re-clustering is performed again for next round.

3 Cluster Structure in Proposed Approach

The proposed approach constructs m-way balanced tree for intra-cluster communication. A network of 100 nodes is considered for cluster structure demonstration. Literature suggests that clustering approach can be of either equal size or unequal cluster size [4]. The cluster structure of proposed approach is shown for both equal and unequal cluster size. Figure 2 shows the cluster formation for equal size clusters, while Fig. 3 shows the cluster formation for unequal cluster sizes. Value of m is 4 (that is also the degree of tree) for the cluster structure. Different levels are demonstrated in different colors.

Fig. 3
figure 3

Unequal size clusters

Full size image

The levels of tree depend on the value of m. Table 1 shows the level of tree with number of nodes at the level corresponding m = 4 and m = 5 for intra-cluster communication. As can be analyzed from Table 1 and cluster structure shown in Figs. 2 and 3 that cluster head receive data from only immediate child and aggregate the data and then send the aggregated data to the base station.

Table 1 Number of nodes at different levels of tree for proposed approach
Full size table

4 Conclusion and Future Work

The work of this paper presented an initial framework of m-way balanced tree data aggregation clustering for wireless sensor networks that reduced the overhead of cluster head. In future, we will analyze the performance of the proposed approach over network metrics such as network lifetime and throughput. We will also analyze the effect of m on network metrics.