Open access peer-reviewed chapter

An Algorithmic Approach to the Node Selection Problem in Industrial Wireless Sensor Networks

By Veeramani Sonai and Indira Bharathi

Submitted: May 8th 2020Reviewed: August 23rd 2020Published: February 3rd 2021

DOI: 10.5772/intechopen.93692

Downloaded: 91

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.

Figure 1.

Simple wireless sensor network.

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 toleranceand 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 becomean 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.

Advertisement

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 Twith non-empty node of set VTand the edge set be ET= {{u,v} u,vVTand uis adjacent to vin Tand uv}.The neighborhoodof a node vof T, NT(v), is the set of vertices adjacent to vin T. The degree of the vertex vis dTv=NTv. ΔTdenotes the maximum degree of a topology T.

3.2 Problem description

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

Given a weighted topology Twith weighted nodes VT=v1vn, and the weighted edges ET. Here, the objective is to find Sv1vnsuch that Sis minimum and for each node in S, say x, covers the maximum subset RNTxsubject to the constraint given in Eq. (1),

yRweightxyweightxE1

where, weightxdenotes the weight of the node xand weightxydenotes the weight of the edge between xand y.

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 Onlogn+nΔlogΔ, where nis the number of nodes and Δis the maximum degree of the topology T.This method choose the node that had maximum node weight value and started assigning the neighborhood nodes with its associated edge weight. Once the sum of edge weight value is larger than the node weight value, then the node is terminated. Furthermore this method does not consider the maximum degree of a node. The sorted nodes are find first and unmarked the rest of the nodes in topology T. Then, for every unmarked node xin the sorted node list, this algorithm requests one more algorithm 1, which allocate sensor node for node x. Next process, the node is marked as xand all nodes assigned to it, and finally node xis added to the necessary set of sink nodes. This step is repeated until all the nodes are marked. The performance measures to the Node_Assignment(W, S, N), where Wdenote the maximum capacity of the node, Sdenote the set of weighted edge value incident on a node, and Nrepresents set of nodes connected with those node. The new node assignment procedure is described in Algorithm 1.

Algorithm 1Node_Assignment(W, S, N).

Require:Consider a set Nconsists of mweighted nodes, say n1,n2,,nmand a set Sof mweighted edges, say e1,e2,,emand the maximum capacity W.

Ensure:The set MNsuch that Mis maximum subject to the constraint

niMeiW

Let M=0.

Sort the edge weights in increasing order, say e1e2,,em.

fori=1to mdo.

ifj=1iejWwhen.

M=MniM

end if.

end for.

returnM.

Algorithm 2Placing_Sink_Nodes.

Require:The weighted topology Twith weighted nodes.

Ensure:Subset of VTto be placed as sink node.

Let Thas nweighted nodes.

Sort the weights of nodes in decreasing order, say w1wn. Let v1,,vnbe the corresponding labels of the nodes.

Let eijdenotes the weight of the edge vivj.

Unmark all the nodes vi,1vin.

fori=0to ndo.

ifviis unmarked then.

Let S=eijvjNTviandvjisunmarked. Let Nbe the set of nodes associated to the vj‘s in S.

Node_Assignment(wi,S,N).

Mark viand mark the nodes assigned to vi.

end if.

end for.

4. Illustration of the proposed capacitated sink node placement problem

Algorithm 2 is traced as follows by using the topology Tas shown in Figure 2. The node with weight value 21has the highest degree so it is chosen for locating the initial sink node. This first node then occupy its neighborhood nodes with weighted values 19, 11, 13since sum of its edge weight value is fewer than or equal to node with value 21(15<21) as given in Figure 3. Likewise, the next node with higher weight value is 20and it can occupy it neighborhood nodes 16, 8, 9since the summation of edge value is smaller (14<20) as shown in Figure 4, which illustrates the result after 20is chosen as a sink node and the final topology is shown in Figure 5.The node spotted in the final topology represents the position of the sink nodes in topology T.

Figure 2.

The topologyT'after placing sink node with node weight 20.

Figure 3.

Given topology T with weights.

Figure 4.

The topologyT'after placing sink node with node weight 21.

Figure 5.

Final topology after placing all the sink nodes.

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 x1,x2,,xsbe the set of nodes of the sorted weights w1,w2,,wsin the given topology Tand let the maximum capacity be W. Thus, w1w2ws.

Let A=a1asbe the output of the algorithm and B=b1bsbe any feasible solution, ai,bi01, 1is. Note that, ai=1(as well as bi=1) denotes the presence of wiin the solution and ai=0(as well as bi=0) denotes the absence of wiin the solution.

Claim 1:If Bis OPTIMUM, then biai.

The algorithm outputs a feasible solution since the number of 1sin OPTIMUMnumber of 1sin any feasible solution. Thus the above claim is true.

Observation 1:There exists a k1nsuch that ai=1,1ik1and aj=0,kjn.

Thus, to show that the algorithm is OPTIMUM, it is required to establish aibi. Towards this end, it is proved that the following sub claim.

Claim 2:If Bis any feasible solution, then aibi.

Proof for claim 2 is by mathematical induction on mbits, where mis the number of bits in which Aand Bdiffer.

Base Case:m=0. Clearly, aibi.

Induction Hypothesis:Consider, the claim is true if they differ in less than m-places, m0.

Induction Step:Let Aand Bdiffer in m+1-places, m0.

Observation 2:Since, Aand Bdiffer in m+1-places there exists j,1jk1such that aj=1and bj=0.

Find the least j1k1such that aj=1and bj=0. Clearly, it can not be the case that jkn. If so, then Bis not a feasible solution.

Now, set bj=1(For example, if A=1,1,1,1,0,00and.

B=1,1,0,0,0,10, then the modified Bis C=1,1,1,0,0,10). By doing this, it is concluded that either the modified B, say C, is feasible or Cis not feasible.

Case 1:Cis feasible.

Number of positions in which Aand Cdiffers is m. By hypothesis, aici. Note that, cibi. Thus, aibi. Hence, the sub claim is true if Cis feasible.

Case 2:Cis not feasible.

Since Cis not feasible, there exists a jknsuch that aj=0and cj=1. Now, set cj=0. This implies, Aand the modified C, say D, differs at m1-places and by the induction hypothesis, aidi. Observe that di=bi. Thus, aibi.

From the above said claims, it is concluded that ai=bi. Hence, the Algorithm 1 provides an optimal solution.

Theorem 1.3 The Algorithm 2 runs in Onlogn+OnΔlogΔ, where nis the number of nodes in the topology T.

Proof.According to the degree of nodes, the nodes are arranged in decreasing order and it takes Onlognas the worst case complexity. The first maximum degree node is passed as input to the Algorithm 1. The same way the algorithm proceeds with the next maximum degree which is not marked and so on which takes the complexity of OΔlogΔ. The Algorithm 1 follows by taking local minimum value and adds to the global sum which satisfies the constraints. The algorithm terminates when it breaks the constraints. Thus, the algorithm produce an optimal solution. So the proposed solution takes the complexity of Onlogn+OnΔlogΔfor identifying and assigning the sink node.

Advertisement

6. Results and discussion

The simulation is done with test data taken from the Internet Topology Zoo Archive [13]. There are 261topologies are available in the data set which indicates a large diversity of network structure. These data sets are gathered from different vendors of networking services. We have made a self written python script to convert Graphical Mark-up Language into adjacency list. The data set contains edge and node informations for the given topology. For a given network, capacity is considered as node value and load is considered as edge weight values. Based on the proposed method, the sink is selected in such a way that the summation of edge weight loads fewer than the total capacity of sink node. The simulation of proposed approach gives us total number of sink nodes required for given topology as shown in the Table 1. It is observed that the average number of sink nodes required to manage the given topology is 56.

Name of the DatasetNumber sink nodes
Abilene4
BelNet5
UniNett6
AtmNet7
Sprint3
Bell Canada4
Garr3
ArpaNet19903
Airtel7

Table 1.

Number of sink nodes vs topology.

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.

© 2021 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Veeramani Sonai and Indira Bharathi (February 3rd 2021). An Algorithmic Approach to the Node Selection Problem in Industrial Wireless Sensor Networks, Wireless Sensor Networks - Design, Deployment and Applications, Siva S. Yellampalli, IntechOpen, DOI: 10.5772/intechopen.93692. Available from:

chapter statistics

91total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Data Aggregation Scheme Using Multiple Mobile Agents in Wireless Sensor Network

By Mohamed Younis Mohamed Alzarroug and Wilson Jeberson

Related Book

First chapter

Processing Carbon Nanotubes

By Brigitte Vigolo and Claire Hérold

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us