Parallel Processing for Range Assignment Problem in Wireless Sensor Networks

Abstract

Wireless sensor network is a collection of autonomous devices called sensor nodes which sense the environmental factors such as temperature, pressure, humidity, moisture, etc. The nodes sense the data, process it and transmit to the other nodes within their transmission range through radio propagation. Energy minimization in wireless sensor networks is a significant problem since the nodes are powered by a small battery of limited capacity. In case of networks with several thousand nodes, the simulation of algorithms can be very slow. The parallel computing model provides significantly faster simulation time for larger networks. Parallel processing involves executing the program instructions by dividing them among multiple processors with the objective of reducing the running time. So, we propose algorithms for the range assignment problem in wireless sensor networks using the parallel processing techniques. We also discuss the complexity of the proposed algorithms and significance of the parallel processing techniques in detail. The proposed techniques will be useful for implementing the distributed algorithms in WSNs.

1. Introduction

In this section, preliminaries of Wireless Sensor Networks (WSNs) and parallel processing are discussed in detail.

1.1 Wireless sensor networks

Wireless Sensor Network (WSN) is a group of spatially dispersed autonomous devices called sensor nodes equipped with a radio transceiver along with an antenna. The devices are responsible for sending and receiving radio signals. Transmission range is assigned to the nodes to facilitate the communication between the nodes of a network. The sensor nodes sense the physical conditions of the environment such as temperature, pressure, sound, heat, light and humidity, etc., at various locations, process the data and transmit to the other nodes that lie within their transmission range through radio propagation. WSN monitors a physical system in real world and has applications in several fields such as environmental monitoring, biological detection, military and health care, etc. [1]. Because of the power constraints for the nodes using batteries with limited capacity, minimization of energy consumption is a significant problem in WSNs [2].

Constructing an efficient topology by assigning transmission range to the nodes of a network to minimize the total energy consumption has become a major challenge in WSNs. In general, the transmission range assigned to a node can be tuned so that the required connectivity constraint for the resultant network is satisfied and the total energy is minimized; this class of problems is categorized as topology control problems [3]. Some of the specified constraints include simple connectivity, bi-connectivity, $k$ -connectivity, etc. [4]. By using an appropriate topology, the energy utilization of the network can be minimized which results in an increased lifetime of a WSN.

Transmission range of a node is the range within which the data sent by other node is received properly [5]. Two nodes in a WSN can communicate if and only if one node is in the transmission range of the other. Transmission range of a node $u$ with the range $r$ in three different dimensions is shown in the Figure 1 . In general, the communication is multi hop in nature, and a node transmits the data to the destination node in its range using the relay nodes. In order to minimize the energy consumption, it is desirable to use short edges rather than the long energy-inefficient edges.

Figure 1.

Radio coverage in different dimensional networks.

Let $P_s$ be the range of source node $u$ to transmit the signal to the destination node $v$ . Then a signal transmitted by the source node $u$ is attenuated by a factor: $P_r\propto \frac{P_s}{\mathit{\text{dist}}{\left(u,v\right)}^{\alpha }}$ , where $\mathit{\text{dist}}\left(u,v\right)$ is the Euclidean distance between $u$ and $v$ , and $\alpha$ is the distance range gradient or path loss coefficient that depends on various environmental factors and generally lies between 2 and 6 [6]. In this chapter, the terms range and power are used interchangeably.

In reality, some problems use mathematical models that describe the problem in a systematic way and enable us to solve the problem efficiently. Graphs can be used to model many relations and represent many physical problems in the real world. A WSN is modeled as an undirected graph to solve the energy minimization problems. In this model, a vertex of the undirected graph represents a node and the edge joining two vertices represents the communication link between the nodes. The nodes are deployed on a Euclidean plane and each pair of two nodes is associated to the Euclidean distance between the nodes. Each node is located by its $x$ and $y$ coordinates and the distance function is used to find the Euclidean distance between any two nodes $x$ and $y$ , and is denoted by $w\left(\mathit{xy}\right)$ which is given by $w\left(\mathit{xy}\right)=\sqrt{{\left(x_1-x_2\right)}^2+{\left(y_1-y_2\right)}^2}$ .

Figure 2 illustrates the graph theoretic modeling of a WSN with four sensor nodes $v_1,v_2,v_3,$ and $v_4$ . In this, Figure 2(a) shows a network of four nodes with their respective transmission ranges and its asymmetric and symmetric versions are shown in Figure 2(b) and (c) , respectively [7]. There is an edge between two vertices in symmetric graph if and only if it is bidirectional. A network is said to be bidirectional if and only if each edge is bidirectional and there exists a bidirectional path between every pair of two nodes of the network. Since the signal transmitted by a sensor node must be acknowledged by the receiver node, the bidirectional links are given preference.

Figure 2.

Illustration of graph theoretic modeling.

Throughout this chapter, the considered topology is bidirectional. Therefore, we use an undirected graph along with the weight function $w$ to represent a WSN. Once a WSN is formulated as an undirected graph $G=\left(V,E,w\right)$ , the transmission range $R\left(v\right)$ assigned to each vertex $v\in G$ is the maximum of all its adjacent edge weights and is mathematically given as follows:

$$R\left(v\right)=\mathit{max}\left\{w\left(\mathit{vu}\right)|\mathit{uv}\in E\left(G\right)\right\}.$$ E1

The total range of the graph which is the sum of the ranges of all the vertices of $G$ is given by $R\left(G\right)={\mathrm{\Sigma }}_{i=1}^{n}R\left(v_i\right)$ . Figure 3 is presented to illustrate the range assignment of a WSN. In this, Figure 3(a) shows a spanning tree of 11 vertices along with weights assigned to the edges and Figure 3(b) shows the range values assigned to the vertices as the maximum of all its adjacent edge weights in the spanning tree, as given in Eq. (1).

Figure 3.

Illustration of range assignment.

Minimum range assignment problem in a WSN is to assign transmission range to the nodes of the network such that the resultant subgraph $H$ satisfies the specified constraints and the total range of the network, i.e., $R\left(H\right)$ is minimized [8]. Let $H$ be a spanning subgraph of the given graph $G=\left(V,E,w\right)$ , $R_H\left(v\right)$ be the range assigned to vertex $v\in V\left(H\right)$ as given in Eq. (1) and $R\left(H\right)$ be total range of the subgraph $H$ . For various problems considered in this chapter, our interest is to find a spanning tree with minimum range.

Chen et al. [9] studied the problem of strong connectivity in multi hop packet radio networks and proposed a 2-approximation algorithm which initially considers an undirected Minimum Spanning Tree (MST) and later establishes the bidirectional connectivity. Strong Minimum Energy Topology problem (SMET) in a WSN is studied by Cheng et al. [10], in which the objective is to assign transmission range to the nodes of the network such that the total range of the network is minimized and the reduced topology is connected. The authors have proved that the SMET problem is NP-complete and proposed two algorithms namely: Minimum Spanning Tree (MST) based Heuristic which is of 2-approximation ratio and an Incremental Power Greedy Heuristic and performed the simulation to show that the Incremental Power Greedy Heuristic performs better than the MST Heuristic. Formulation of the SMET problem is as follows:

Problem: Strong Minimum Energy Topology problem (SMET).

Instance: A complete graph $G=\left(V,E,w\right)$ , where $w:V\times V\to {\mathbb{R}}^{+}$ is a weight function.

Question: A range assignment such that the induced subgraph $H$ is connected and the and the total range of $H$ , i.e., $R\left(H\right)$ is minimized.

1.2 Parallel processing

Large scale WSNs such as environmental monitoring systems produce large amount of data in the order of Peta bytes. The challenges in this case are storage and computation as the sensors are constrained by their resources which are scarcely available [11]. If the large amount of data is processed centrally, all data needs to be transmitted to a central server using multi hop transmissions which leads to high computational cost. One of the best ways to avoid such problem is to exploit the advantages of the distributed storage and parallel processing. Instead of transmitting data to a central server, data is stored and processed in network which reduces the computational cost. In this process, the computational task is decomposed into many small tasks, and the computation is executed in parallel by the distributed sensors.

Sullivan et al. [12] proposed a set of new parallel algorithms for a tree decomposition-based approach to solve the maximum weighted independent set problem. Independent set problem for a given graph is to find a subset of vertices with maximum cardinality such that no two vertices in the graph are adjacent to each other. Maximum Weighted independent set problem in which, the vertices are assigned weights, is to find an independent set with maximum weight [13]. Zhu et al. [14] proposed parallel algorithm for the hierarchical-based protocol for WSNs based on the Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm in order to improve the routing efficiency of the networks. Authors have implemented the algorithms using the parallel processing technique and showed that this technique has increased the overall performance. Lounis et al. [15] presented a new model for parallel computing of energy consumption in WSNs, and implemented on GPU architecture. Through simulation, authors showed that the proposed model provides simulation times significantly faster than that of the sequential model for large networks and for long simulations.

Andoni et al. [16] gave algorithms for geometric graph problems in the modern parallel models. The authors found a $\left(1+\mathrm{ϵ}\right)$ approximation algorithm for a Geometric Minimum Spanning tree (MST) problem. In geometric MST, set of $n$ points are plotted on a low dimension space such as $R^d$ and other bounded metric spaces, in which weights of the edges are the distances between their endpoints. Authors also gave a general algorithmic framework that also applies to Earth-Mover Distance and the transportation cost problem. Katsigiannis et al. [17] presented a Helper Threading scheme for parallelizing the Kruskal’s algorithm [18] which is used for finding a Minimum Spanning Forest (MSF). The implementation employs one main thread, which executes the serial algorithm, and several helper threads, that run in parallel and reduce the work of the main thread.

In this chapter, we discuss the parallel processing techniques for the range assignment problem for simple connectivity. We propose algorithms for this problem using parallel processing techniques and determine the complexity. The proposed algorithms initially find an MST and assign range to each vertex of the network based on its range in the Euclidean MST. We find the Euclidean MST using well known algorithms: Prim’s and Kruskal’s and later we assign the range using parallel processing technique for both the cases. We also discuss the complexity of the proposed algorithms in detail for both the algorithms.

Simulation is an act of imitating operation of real world process or system over time [19]. The simulation is performed on a model which represents the system. It is known that simulations closely reflect accurate behavior of the system. Simulations help in evaluating the algorithm before investing on the physical hardware.

2. Related work

Finding a Euclidean MST is an important problem in Graph Theory and there are several algorithms in the literature [20]. MST problems have significant applications in computer and communication network design, as well as indirect applications in fields such as computer vision and cluster analysis [21]. Parallelization of Prim’s algorithm is studied by Deo and Yoo [22] and the proposed algorithms used shared memory computers. Gonina et al. [23] studied the parallel implementation of the Prims’s algorithm for finding the MST of dense graphs. Authors presented the simulation results which demonstrate the advantage of proposed algorithms.

Vladimir et al. [24] studied serial variants of Prim’s and Kruskal’s algorithm and presented their parallelization, targeting message passing parallel machine with distributed memory. Authors have considered large graphs and presented experimental results which show that Prim’s algorithm is a good choice for dense graphs while Kruskal’s algorithm is better for sparse graphs. Authors have proposed algorithms based on the sequential algorithms of Prim and Kruskal, targeting message passing parallel machine with distributed memory. The proposed algorithm which uses the Prim’s algorithm has a running time of $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ and the one which uses the Kruskal’s algorithm has a running time of $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ where $n$ is the number of vertices and $k$ is the number of partitioned subsets of $V$ such that each subset has $\frac{n}{k}$ consecutive vertices and their edges. In this section, we discuss the parallel processing algorithms for computing Euclidean MST using both Prim’s and Kruskal’s algorithms separately. In both the algorithms, each processor gets a subset of vertices from the given set of vertices to process.

The considered input for the parallelization of both Prim’s and Kruskal’s algorithm by Vladimir et al. [24] is an undirected simple graph with weights assigned to the edges. For our research the input considered is a complete graph along with edge weights, where the edge weights are the Euclidean distance between the nodes.

2.1 Parallelization of Prim’s algorithm by Loncar et al.

Prim’s algorithm starts from an arbitrary vertex and then grows the subtree by choosing a new vertex from the set of unvisited vertices and adding it to the subtree in each iteration. The Prim’s algorithm runs until the number of edges becomes $n-1$ or all the vertices are added to the subtree. The complexity of the Prim’s algorithm is $O\left(n^2\right)$ where $n$ is the number of vertices of the given graph. In this algorithm, the input considered is an undirected graph with $n$ vertices and $m$ edges along with the edge weights in which weight of edge $\mathit{uv}$ is denoted by $w\left(\mathit{uv}\right)$ [24].

The weights are represented using the adjacency matrix which is defined as follows:

$$a_{\mathit{ij}}=\left(\begin{array}{cc}w\left(v_i{v}_j\right)& \text{if}\left(v_i{v}_j\in E\right)\\ 0& \text{otherwise}.\end{array}\right.$$ E2

Prim’s algorithm is implemented using the auxiliary array $d$ of length $n$ which stores the weights from each vertex to the MST. The lightest weight edge is chosen from $d$ and is added to MST in each iteration and the array $d$ is updated accordingly. The main loop of the Prim’s algorithm cannot be parallelized since the minimum edge weights incident to MST change in each iteration. So, only two steps are parallelized: finding a minimum weight edge that connects a new vertex not in MST to a vertex in MST and updating the array $d$ . The complexity of the proposed algorithm is $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ where $n$ is the number of vertices and $k$ is the number of processors.

2.2 Parallelization of Kruskal’s algorithm by Loncar et al.

Kruskal’s algorithm finds a minimum weighted edge which connects two components in the forest in each iteration, i.e., it grows multiple trees in parallel. Initially, Kruskal’s algorithm creates a forest considering each vertex as a tree and next it sorts all the edges. Each time a minimum weighted edge is chosen and added to the forest if it connects two different trees else it is discarded. This process is repeated until the forest becomes a spanning tree. The complexity of the proposed algorithm is $O\left(mlogn\right)$ where $m$ is the number of edges and $n$ is the number of vertices [24].

Similar to the Prim’s algorithm, we have adjacency matrix which stores the weights between the vertices, and each processor is assigned a subset of vertices. In parallelization of Kruskal’s algorithm, each processor sorts the edges of its vertices according to their weights. At each process, a local MST is found using Kruskal’s algorithm and finally, all the local MST’s are merged. The complexity of the proposed algorithm is $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ where $n$ is the number of vertices and $k$ is the number of processors.

3. Parallelization of range assignment problem

In this section, we present the proposed algorithms for range assignment problem using parallel processing techniques. The proposed algorithms adopt the algorithms for parallelization of both Prim’s and Kruskal’s algorithms by Loncar et al. [24]. In this environment, the nodes are deployed on a Euclidean plane and each pair is associated with the Euclidean distances between those nodes. Since a WSN is modeled as an undirected graph along with a weight function, the input for these algorithms is a complete graph $G=\left(V,E,w\right)$ where the weight function is as explained in Section 1. The range assigned to a vertex $v$ is denoted by $R\left(v\right)$ .

Objective of this problem is to find a spanning tree such that the total range of the spanning tree is minimized. In the proposed algorithms, we initially find the spanning tree of the given complete graph and assign the range to the vertices based on their range in the Euclidean MST using parallel processing. We propose two algorithms: one using the Prim’s algorithm and the other using the Kruskal’s algorithm. We also compute the complexity of the proposed algorithm in both the cases. The list of notations used in this chapter is given in Table 1 .

Notation	Explanation
$V$	Set of vertices
$E$	Set of edges
$n$	Number of nodes
$w\left(\mathit{uv}\right)$	Euclidean distance between $u$ and $v$
$R\left(v\right)$	Range of vertex $v$
$d$	Auxiliary array
$P$	The set of processors
$p_i$	$i^{\mathit{th}}$ processor
$k$	Number of processors
$T$	Resultant spanning tree

Table 1.

List of notations.

3.1 Range assignment using Prim’s algorithm

Let $G=\left(V,E,w\right)$ be the given complete graph. In this algorithm initially, we find a spanning tree by parallelizing the Prim’s algorithm and range is assigned to the vertices based on their range in the MST by using parallel processing. The formulation of the problem is as follows:

Problem: Parallel Algorithm for Range assignment using Prim’s algorithm (PARA-Prim’s).

Input: A complete graph $G=\left(V,E,w\right)$ , where $w$ is a weight function and $P$ the set of processors.

Objective: To find a spanning tree such that the total energy is minimized, using parallel processing.

In the proposed algorithm, we consider a complete graph and the number of processors as input and compute a spanning tree which minimizes the total range. In this algorithm, we partition the vertices into $k$ groups and each processor gets $\frac{n}{k}$ consecutive vertices and their edges. Each processor also contains auxiliary array $d$ of the vertices which maintains the distances of the vertices to the MST. Let $V_i$ and $d_i$ be the set of vertices and the auxiliary array of the processor $p_i$ , respectively.

Each process finds a minimum weighted edge which connects the MST with vertices of the set $V_i$ and sends to the leader processor using all-to-one reduction. The leader processor selects one with the minimum weight among all the received edges, adds it to MST and broadcasts to all the processors. Processors mark the vertices connected to MST and update their auxiliary array $d$ and this process is repeated until all the vertices are added to the subtree.

Next, we assign range to the vertices in the following way: for a vertex, each process finds the farthest vertex to it in the MST and sends the distance between them to the leader processor using all-to-one reduction. Later, leader processor selects one with maximum edge weight among all the received edge weights and that weight is assigned as range to the vertex $v$ . This process of range assignment is repeated for all the vertices. The sequence of steps is presented in Algorithm 1.

Theorem 1.1 [24] The parallelization of Prim’s algorithm takes $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ running time where $n$ is the number of nodes and $k$ is the number of processors.

Theorem 1.2 The algorithm PARA-Prim’s takes $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ running time, where $n$ is the number of nodes and $k$ is the number of processors.

Proof: From Theorem 1.1, it is clear that finding the MST by parallelizing the Prim’s algorithm takes $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ running time for $n$ number of nodes and $k$ number of processors. In PARA-Prim’s algorithm the range assignment is done based on the MST obtained by parallelizing the Prim’s algorithm. For each vertex, we find the farthest vertex in each processor which takes the running time of $O\left(\frac{n}{k}\right)$ and for all such vertices it takes a running time of $O\left(\frac{n^2}{k}\right)$ . Next each processor sends the farthest vertex to the leader process and leader processor finds the global farthest vertex which takes a running time of $O\left(\frac{n}{k}\right)$ and for all such $n$ vertices it takes a running time of $O\left(\frac{n^2}{k}\right)$ . So the running time of PARA-Prim’s algorithm is $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ .

3.2 Range assignment using Kruskal’s algorithm

Similar to the Prim’s algorithm in this algorithm, we have $k$ number of processors assigned with $\frac{n}{k}$ set of consecutive vertices. Each processor sorts the edges of its vertices and finds a local MST using the Kruskal’s algorithm. Finally all the local MSTs are merged in the following way: first processor sends its set of edges of the local MST to the second processor and forms a new local MST by using the set of edges from both the processors. Now, the first process remains no longer and terminates, and this process of merging continues until single process remains. Range assignment is done to the vertices in parallel way similar to the PARA-Prim’s algorithm as explained in the previous subsection. The formulation of the problem is as follows:

Problem: Parallel Algorithm for Range assignment using Kruskal’s algorithm (PARA-Kruskal’s).

Input: A complete graph $G=\left(V,E,w\right)$ , where $w$ is a weight function and $P$ the set of processors.

Objective: To find a spanning tree such that the total energy is minimized, using parallel processing.

The sequence of steps for the above explained procedure is presented in Algorithm 2 named PARA-Kruskal’s.

Theorem 1.3 [24] The parallelization of Kruskal’s algorithm takes $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ where $n$ is the number of vertices and $k$ is the number of processors.

Theorem 1.4 The algorithm PARA-Kruskal’s takes $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ running time, where $n$ is the number of nodes and $k$ is the number of processors.

Proof: From Theorem 1.3, it is clear that, the running time of the parallelization of Kruskal’s algorithm is $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ . Next, we do the range assignment to the vertices based on its range in the MST formed by parallelizing the Kruskal’s algorithm. From Theorem 1.3, it is clear that the running time of the range assignment for all the vertices is $O\left(\frac{n^2}{k}\right)$ . So, the running time of the PARA-Kruskal’s algorithm is $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ .

4. Comparison with the state of arts

Solving the range assignment problem by computing Euclidean MST using Prim’s algorithm and Kruskal’s algorithm takes running time of $O\left(n^2\right)$ and $O\left(n^{2}logn\right)$ , respectively. For WSNs with large number of sensor nodes, this complexity is quite high which can be improved by using parallel processing techniques. Simulation can be performed on hardware that supports multiple cores in order to realize the improvements over serial programming environments. The complexities of the range assignment problem using Prim’s algorithm and Kruskal’s algorithm by employing parallel processing techniques are $O\left(\frac{n^2}{k}\right)+O\left(nlogk\right)$ and $O\left(\frac{n^2}{k}\right)+O\left(n^{2}logk\right)$ , respectively. So, theoretically there is a significant improvement in the complexity of the range assignment problem by applying parallel processing techniques. Simulation can be performed to study the stability of the proposed algorithms and to compare the proposed algorithms with the existing algorithms for the range assignment algorithms.

5. Conclusions

In this research, we have studied the range assignment problem by employing parallel processing techniques of both Prim’s and Kruskal’s algorithms. The complexity of the proposed two algorithms is discussed in detail and it is shown that complexity can be improved by using parallel processing techniques for larger networks. It is an interesting problem to study variations of range assignment problems using parallel processing techniques. The implementation of the proposed algorithms can be realized using CUDA programming which supports programming GPU with multiple cores.

Abbreviations

WSN	wireless sensor network
MST	minimum spanning tree
MSF	minimum spanning forest
PARA	parallel algorithm for range assignment