ABSTRACT

Wireless multimedia sensor network (WMSN) consists of sensors that can monitor multimedia data from its surrounding, such as capturing image, video and audio. To transmit multimedia information, large energy is required which decreases the lifetime of the network. In this paper we present a clustering approach based on spectral graph partitioning (SGP) for WMSN that increases the lifetime of the network. The efficient strategies for cluster head selection and rotation are also proposed.

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 e_ij. 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 a_ij is the number of edges from node i to node j, and the diagonal entry a_ii 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. λ₁ represents the number of subgraphs in the network. The second smallest eigenvalue λ₂ 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 λ₂. 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 deg_i 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 λ₂ of Laplacian matrix.

• Choose eigenvector value corresponding to the eigenvalue λ₂.

• 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.

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.

Cluster head rotation must take place when residual energy of the cluster head node falls below the

Table 4. Clustering after second iteration.

threshold value. The present cluster head declares the election process by sending a message that contains its E_res to all the cluster members. The cluster members whose residual energy is greater than E_res 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, Dⁱ 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.

REFERENCES