Clustering in Wireless Multimedia Sensor Networks Using Spectral Graph Partitioning ()
1. Introduction
Wireless sensor network (WSN) consists of hundreds or even thousands of sensor nodes that are powered by small irreplaceable batteries. The sensors, which are randomly deployed in an environment, should collect data from their surrounding, process the data and finally send it to the sink through multi hops [1]. There are many applications where sensor nodes are deployed onto roads, walls or unreachable place and they sense a variety of physical phenomena such as traffic on the road, temperature, pressure or detect forest fires to aid rapid emergency response. WSN has limited resources such as less communication bandwidth, limited energy supply, less storage and less computing power [2].
Wireless multimedia sensor network (WMSN) has been possible due to the production of cheap CMOS (Complementary Metal Oxide Semiconductor) camera and microphone sensors which can acquire multimedia information. WMSN consists of camera sensors as well as scalar sensors. Camera sensors can retrieve much richer information in the form of images or videos and hence provide more detailed and interesting data about the environment [3]. Scalar sensors can retrieve the scalar phenomena like temperature, pressure, humidity, or location of objects [4]. Camera sensors may generate very different views of the same object if they are taken from different viewpoints [5].
Sensor nodes (SN) are deployed in remote and hostile environment, so it is difficult to replace the batteries. They are densely deployed to monitor the physical environment. In case of WMSN, the neighboring sensors would produce similar data and transmit such data to the sink. During this transmission of data, a large amount of energy is consumed. To reduce the energy consumption some kind of grouping of sensor nodes can be done to form clusters. Inside every cluster, one node acts as cluster head (CH). Cluster head is responsible for communication with other cluster heads. Cluster head collects data from all the nodes within its cluster, aggregates this information and then transmits to the sink through other CHs using multi hop communication [2]. Figure 1 shows the clustering of nodes in a general WSN. In WMSN, the volume of multimedia data to be transmitted is very large, therefore, more energy consumption occurs during communication [6].
In this paper, we propose a clustering and cluster head selection approach. Spectral graph partitioning (SGP) technique based upon eigenvalues proposed by Fiedler has been utilized for WMSN [11]. SGP method has been used in many applications such as image segmentation, social networks, etc. [2].
The spectral graph partitioning (SGP) algorithm is based on second highest eigenvalues of particular graph. The second smallest eigenvalue of the Laplacian matrix corresponding to different eigenvectors, is used to partition the graph into two parts. Within a cluster, a node with highest eigenvalue is selected as cluster head. In case of WMSN, large volume of sensed data is generated, therefore, such clustering can be utilized to reduce the volume and number of data transmissions through data aggregation. In this paper, we have shown formation of clusters and CH selection using SGP for given WMSN.
The rest of the paper is organized as follows. Section 2
reviews the related work. General SGP strategy for clustering has been presented in Section 3. Section 4 describes the use of SGP for WMSN. Section 5 concludes the paper.
2. Related Work
Clustering in WSN is a process in which set of sensor nodes are loosely connected and work together. All the nodes in the cluster elect one cluster head which is responsible for data aggregation and data transmission and maintaining connectivity between other cluster heads.
Brahim Elbhiri et al. [6] suggested spectral classification based on near optimal clustering in wireless sensor networks (SCNOPC-WSN) algorithm. This algorithm deals with the clustering problem in WSN. Energy aware adaptive clustering protocol is used for the bi-partitioning spectral classification and it guarantees robust clustering. SCNOPC-WSN also deals with the optimization of the energy dissipated in the network.
M. Chatterjee et al. [7] suggested the weighted clustering algorithm (WCA) for ad hoc networks. WCA uses the on-demand clustering algorithm in multi hop radio networks. WCA elects the head nodes on the basis of neighboring nodes and their sending capabilities.
Banerjee and Khuller [8] suggested hierarchical clustering algorithm based on geometric properties of the wireless network. Generic graph algorithms developed for arbitrary graphs would not exploit the rich geometric information present in wireless network. Clustering problem in a graph is theoretical framework and presents an efficient distributed solution.
Adaptive Clustering Protocol is proposed by A. Garg and M. Hanmandlu [9]. It divides the network into several systematized hexangular and chooses the closest node to each hexangular as the head node for it. The nodes with the maximum amount of residual energy is selected as a cluster head.
Lu Dian et al. [10] proposed a clustering based spectrum allocation scheme for efficient spectrum allocation in cognitive radio networks. Spectral graph partitioning theory is used to divide a graph into clusters so that spectrum allocation is executed in parallel.
3. Cluster Handling Using SGP
Spectral graph partitioning technique uses information obtained from the eigenvalues and eigenvectors of their adjacency matrices for partitioning of graphs. The methods are called spectral, because they make use of the spectrum of the adjacency matrix of the data to cluster the points [11]. Spectral methods are widely used to compute graph separation. Spectral graph partitioning is a powerful technique in data analysis that has found increasing support and applications in many areas such as image segmentation and social network analysis. SGP divides the graph into two disjoint groups, based on eigenvectors corresponding to the second smallest eigenvalue of the Laplacian matrix [10].
Let 
is an undirected graph where V represents the set of vertices (nodes) and E represents the set of edges connecting these vertices. Each vertex is identified by an index 
The edge between node i and node j is represented by eij. The graph can be represented as an adjacency matrix. The adjacency matrix A of graph G having N nodes is the 
matrix where the non-diagonal entry aij is the number of edges from node i to node j, and the diagonal entry aii is the number of loops at node i. The adjacency matrix is symmetric for undirected graphs [12].
The adjacency matrix A is defined as
We also define degree matrix D for graph G. The degree matrix is a diagonal matrix which contains information about the degree of each node. It is used together with the adjacency matrix to construct the Laplacian matrix of a graph. The degree matrix D for G is a 
square matrix and is defined as
The Laplacian matrix is the combination of adjacency matrix and the degree matrix. The Laplacian matrix of the graph G having N vertices is 
square matrix and is represented as
The normalized form of Laplacian matrix can be written as
The eigenvalues of matrix 
are denoted by
, 
such that 
Laplacian matrix has the property 
where X is the eigenvector of the matrix 
and λ is the eigenvalue of the matrix
. Laplacian matrix plays important role in spectral graph theory. λ1 represents the number of subgraphs in the network. The second smallest eigenvalue λ2 is referred to the algebraic connectivity and its corresponding eigenvector is usually referred to as the Fiedler Vector [13].
We choose the eigenvector values corresponding to the second smallest eigenvalue λ2. Second highest eigenvalue 
divides the graph into two subgraphs. G is divided into two subgraphs G+ and G−, where G+ and G− are the set of vertices related to the new subgraphs. G+ contains nodes corresponding to positive eigenvalues and G− contains nodes corresponding to negative eigenvalues. The set of vertices is defined by 
such that
, where
, 
and
.
Based on the above concept, in next section we have proposed a new approach to partition the WMSN into the clusters.
4. Cluster Formation in WMSN
Here we apply the SGP technique to partition the network. SGP has many advantages as compared to other clustering algorithms. While clustering, it results in few links to other clusters but intra-cluster communication is high. Each node is at one hop distance from other node within the cluster. If the graph is to be partitioned into more than two subgraphs, apply SGP technique recursively. High intra-cluster similarity between the nodes makes SGP technique a better option for multimedia data clustering.
In our proposed method, clustering of WMSN has been done by applying Spectral Graph Partitioning technique [10] recursively. Each node sends short message to sink which contains the location information of the node. On the basis of this information, the sink constructs the adjacency matrix and degree matrix and then constructs the Laplacian matrix. The eigenvector corresponding to second smallest eigenvalue (called Fiedler Vector) is used to partition the WMSN. The location of each node may be found by GPS (Global Positioning System) or any other localization method [14,15].
• 4.1. Steps for Clustering
• Construct a graph G for the given sensor network.
• Construct the normalized Laplacian matrix, defined as
where degi is the degree of node i.
• Form the Laplacian matrix 
of the graph. Compute the eigenvalues and eigenvector of Laplacian matrix.
• Select the second smallest eigenvalue λ2 of Laplacian matrix
.
• Choose eigenvector value corresponding to the eigenvalue λ2.
• Divide the graph G into two sub-graphs G+ and G−, where G+ contains nodes corresponding to positive eigenvalues and G− contains nodes corresponding to negative eigenvalues.
After the first iteration of above algorithm, the whole network is divided into two clusters based on the eigenvalues of the nodes. Table 1 shows the two partitions/ clusters for a given graph shown in Figure 2. After first iteration cluster 1 contains all the nodes with positive eigenvector values and another cluster 2 contains nodes having negative eigenvector values. Cluster 1 has six nodes A, B, C, D, E, and G with positive values of eigenvector. Cluster 2 has six nodes F, H, I, J, K and L that have negative eigenvector values. These clusters are listed in Table 2.
Only two clusters are formed in first iteration as shown in Figure 3. The larger cluster can be further divided into
Table 1. Eigenvector table and clustering of given network.
Figure 3. Clustering after first iteration.
two different clusters by applying the algorithm recursively. This process continues until maximum intra-node distance within a cluster is less than 
where R is the transmission rang of the sensor node. When intranode distance within a cluster is less than 
two nodes in neighboring clusters can communicate in one hop. After applying the algorithm recursively, the given network is divided into four clusters as shown in Figure 4.
It has been observed that both the clusters have higher intra-node distance than 
so apply the algorithm to both the clusters. After applying the algorithm cluster 1 is portioned into two different clusters. This algorithm is also applied to cluster 2 of Figure 3.
Thus the whole network is divided into four clusters as shown in Figure 4. Table 3 shows different nodes present in the each cluster.
4.2. Cluster Head Election
The clustering algorithm divides the whole network into clusters. The next step is election of cluster head for each cluster. As per the property of SGP, the least eigenvector value of node signifies that the node is well connected to the other nodes within the cluster as well as it is connected to cluster [13].
For initial cluster head election, we chose the least eigenvector value among the nodes within cluster. Table 4
Table 2. Initial cluster for the network.
Table 3. Final clusters for the network.
represents the eigenvector values of the cluster and Table 5 shows the elected cluster heads in different clusters on the basis of eigenvector values. Therefore, we compare the eigenvector values of the cluster and choose the least eigenvector node as a cluster head, i.e.
Figure 5 shows the elected cluster heads for different clusters.
Cluster head rotation must take place when residual energy 
of the cluster head node falls below the
Figure 5. Elected cluster heads for different clusters.
Table 4. Clustering after second iteration.
threshold value
. The present cluster head declares the election process by sending a message that contains its Eres to all the cluster members. The cluster members whose residual energy is greater than Eres responds to this
Table 5. Elected cluster heads.
message by sending the residual energy to the cluster head.
The new cluster head is elected based upon CH Candidacy Factor 
defined as
where 
is the residual energy of node i, Di is the distance between node i and current cluster head. If 
and 
are the location coordinates of current cluster head and node i, respectably, then
A node with highest value of CF is elected as next cluster head.
5. Conclusion
This paper has proposes an approach to deal with the clustering problem in a given wireless multimedia sensor network. The proposed algorithm partitions the given WMSN into clusters such that nodes in a cluster are highly correlated and intra-cluster association is minimized. In WMSN where nearby nodes have common interest in terms of sensing, our proposed algorithm is more suitable. Further we define the algorithm for cluster head election and rotation. The given strategy can be used in WMSN to prolong the network lifetime.