Number of sink nodes vs topology.

## Abstract

Industrial Wireless Sensor Networks (IWSN) are the special class of WSN where it faces many challenges like improving process efficiency and meet the financial requirement of the industry. Most of the IWSNs contains a large number of sensor nodes over the deployment field. Due to lack of predetermined network infrastructure demands, IWSNs to deploy a minimum number of sink nodes and maintain network connectivity with other sensor nodes. Capacitated Sink Node Placement Problem (CSNPP) finds its application in the Industrial wireless sensor network (IWSN), for the appropriate placement of sink nodes. The problem of placing a minimum number of sink nodes in a weighted topology such that each sink node should have a maximum number of sensor nodes within the given capacity is known as Capacitated Sink Node Placement Problem. This chapter proposes a heuristic based approach to solve Capacitated Sink Node Placement Problem.

### Keywords

- industrial wireless sensor networks
- sink node
- capacitated sink node
- node placement
- wighted topology

## 1. Introduction

Traditionally, the industries are automating their system using wired communications. The wired communication requires quite expensive communication channels and also it needs to be monitored regularly. Due to the high cost incurred in maintaining the wired system, most of the industries not implementing it. Therefore, cost-effective and alternative to wired system needs to be implemented in the industries. Due to recent growth of wireless sensor network (WSN), demands improvement of product development and service provisioning process for the industrial applications. Due to recent enhancement in the wireless sensor network (WSN), the realization of industrial automation can be feasible using WSN. Figure 1 shows a simple structure of wireless sensor network. In WSN, a small sensor unit is attached to every industrial equipment to monitor the environmental parameters like humidity, temperature, pressure etc., Since all the nodes are not actively participating in the data collection process only some the nodes will be used to gather the data from different sources and these nodes are known as *sink node*. This measured information is transmitted to the sink node and the to the common gateway. Finally, the data will be sent the users through Internet where gateway is connected. In this regard, WSN is widely used to create industrial wireless sensor network (IWSN) that rapidly responses to the real-time events.

Recently, there are many research activities mainly focusing on developing a method to address the challenges like Quality-of-Service (QoS [1, 2]), data redundancy, resource constraints, security, large-scale deployment in the IWSN. In a large-scale network, having single sink node has some disadvantages related to performance and scalability. In such case, the amount of sink nodes in the network has to be increased to overwhelm sink node failure. Hence a better solution for this problem is the usage of multiple sink nodes. Most of the researches are also not focused on the task of multiple sink nodes in the sensor network. So in this chapter, we are concentrated on deploying and handling multiple node in the sensor network.

The sink node deployment problem impacts in flow *set-up time, fault tolerance* and *reliability*. These issues include deployment of sink nodes in the specified topology and decide the minimum number of sink nodes required for the same topology. Each node in the topology is connected with weight value known as capacity and each edge is said to be connected with weight value called processing request to the sensor. Deployment of least number of sink node in a specified network topology *will reduce the sink nodes and interaction time between the sensor nodes become* an NP-Hard problem [3]. Thus defining the optimal number of sink nodes is a challenging problem in the Industrial Wireless Sensor Networks (IWSN) because this affects many metrics in the network. In early, sink node placement problems use interaction time between the sensor node and the sink node as metric for each sink node. Those approaches do not consider the situation when the sink node failure happens. So, each sink node has been assigned a maximum (request processing) load apart from considering interaction time. The load applied to process the real-time actions determine the availability as well as the efficiency of the network. Hence the sink node offer the satisfactory resources to implement such actions. The load for the sink node is considered based on the number of actions arrived. Due to insufficient capacity of sink node, to manage resources like processor, bandwidth and memory. In this chapter, the sink node is defined as capacitated which denotes the maximum number of actions are to be processed by the sink node. While choosing the sink node to control different sensor node, the communication time among sensor node and sink node should be reduced in case, if the nodes are said to be near to each other. If both sensor and sink node are far away, then it takes more time to interact with one another. The core objectives of load consideration for every sink node are as follows:

Every sensor node has a restriction on memory and processing of each action, only limited number of requests are processed by the sink node.

As the load of the sink node increases, it fails to handle the request more than its maximum capacity. This will leads to increase of sink node and sensor interaction time.

If single sink node fails then it may affect another sink node.

The sink node and sensor node communication time plays an essential parameter in the deployment of sink node. A simple approach is, the sensor node is said to be connected with the nearest selected sink node. But this method fails to work properly due to the limitation of load on each sink node. To overcome this issue, the sensor node connecting to the sink node should be stopped as long as it maximum load is reached. The main objective here is to place a minimum number of sink node in the network. This work also focused on reducing the interaction time between sink node and sensor node. This work proposes an efficient heuristic method to resolve Capacitated Sink Node Placement Problem.

## 2. Literature survey

IWSNs brings several advantages over wired industrial automation like monitoring and control [4, 5, 6]. In order to utilize the benefits of IWSNs, effective communication system needs to be maintained. Such system should address the unique challenges in the IWSNs. In this regard, many researchers working hard to find the solution to the IWSNs challenges especially establishing and maintaining network connectivity. In a large-scale network, identifying the minimum number of sink nodes and its appropriate placement becomes NP-Hard problem [3, 7, 8, 9, 10, 11, 12].

## 3. Problem statement

### 3.1 Prefaces

Assume a simple connected topology be

### 3.2 Problem description

Capacitated Sink Node Placement Problem (CSNPP) is defined as follows:

Given a weighted topology

where,

### 3.3 The solution for the capacitated sink node placement problem (CSNPP)

The node placement problem in the network becomes NP-hard [3]. An efficient heuristic method is applied to provide a solution to this problem. The proposed method implements a novel algorithm with the time complexity of

**Algorithm 1** Node_Assignment(

**Require:** Consider a set

**Ensure:** The set

Let

Sort the edge weights in increasing order, say

**for****do.**

**if****when.**

**end if.**

**end for.**

**return***M.*

**Algorithm 2** Placing

**Require:** The weighted topology

**Ensure:** Subset of

Let

Sort the weights of nodes in decreasing order, say

Let

Unmark all the nodes

**for****do.**

**if****then.**

Let

*Node**Assignment(**).*

Mark

**end if.**

**end for.**

## 4. Illustration of the proposed capacitated sink node placement problem

Algorithm 2 is traced as follows by using the topology

## 5. Theoretical analysis of proposed approach

For any given output sink node, the maximum capacity is satisfied according the constraint (max. capacity) defined and also all the nodes in the given topology is covered completely.

Theorem 1.1 The solution to the Algorithm 2 is feasible.

**Proof:** The algorithm is proceeds by marking a node as sink node and also label all the nodes covered by the marked sink node. If unmarked nodes are found, then the algorithm is terminated. Henceforth, in a given topology all nodes are covered completely. Furthermore, the proposed solution 1, does not allow the node capacity beyond its maximum defined capacity. Hence, it is proved that the proposed algorithm is feasible.

The proposed approach uses greedy strategy and gives the approximate solution. For a given instance of proposed approach *Node**Assignment()*, it always provides the optimal solution.

Theorem 1.2 The solution to the Algorithm 1 is optimum.

**Proof:** Let

Let

**Claim 1:** If

The algorithm outputs a feasible solution since the number of

**Observation 1:** There exists a

Thus, to show that the algorithm is

**Claim 2:** If

Proof for claim 2 is by mathematical induction on

*Base Case:*

*Induction Hypothesis:* Consider, the claim is true if they differ in less than

*Induction Step:* Let

**Observation 2:** Since,

Find the least

Now, set

**Case 1:**

Number of positions in which

**Case 2:**

Since

From the above said claims, it is concluded that

Theorem 1.3 The Algorithm 2 runs in

**Proof.** According to the degree of nodes, the nodes are arranged in decreasing order and it takes

## 6. Results and discussion

The simulation is done with test data taken from the Internet Topology Zoo Archive [13]. There are

Name of the Dataset | Number sink nodes |
---|---|

Abilene | 4 |

BelNet | 5 |

UniNett | 6 |

AtmNet | 7 |

Sprint | 3 |

Bell Canada | 4 |

Garr | 3 |

ArpaNet1990 | 3 |

Airtel | 7 |

## 7. Conclusion and future work

This chapter proposes an efficient algorithm to place the sink node for the given topological network. This algorithm reduces cost by reducing the number of the sink node being used in the network. Moreover, the placed sink node can serve a maximum number of sensor nodes. The future work is to enhance this approach when a sink node fails in the given topology.