Modified Particle Swarm Optimization in Wireless Sensor Network for Clustering and Routing

Abstract

Wireless sensor networks are composed of sensor nodes and are being deployed in many applications, where security is deemed critical. In WSN, the data collected at any node is forwarded to any designated sink node either through single or multiple hops. Due to the weaker nature and intrinsic, they are easily brought down by external security attacks. The routing plays a vital role in forwarding data from one node to another. Optimal route discovery in WSN is often problematic due to several factors like drain of energy in the node and so on. The residual energy of nodes located near the sink area has the high probability of getting drained out sooner than nodes in other areas. The proposed research addresses this issue through an energy-efficient clustering technique and trustable routing protocol specifically designed for WSNs that minimize the energy consumed by the nodes at the sink area. In this work, a novel clustering algorithm based on modified particle swarm optimization (MPSO) technique had been proposed to form clusters that engage in selecting the cluster heads at the sink coverage area and account for devising a solution to the energy hole problem. Also an energy trust system (ETS) for WSNs had been formulated in the proposed research for effectively detecting the Sybil attacks. Multi-level detection based on identity and position verification is carried by the proposed ETS. Cluster-based trust-aware secure routing had been performed in the proposed research that successfully detects the available active nodes prior to forwarding any data and establishes alternate routes, if need arises. The main aim of the proposed research is to preserve energy of nodes and improvise the security of data while routing from source to sink nodes.

1 Introduction

The wireless sensor network is advancing in recent years. The sensor devices are mostly used as input devices to detect physical or environment conditions. In this, node to node data transmission is done by calculating base station distance using various algorithms.

A wireless sensor network is composed of numerous tiny sensors that monitor and track information about the environment in which they are deployed. The aggregated information is transmitted through wireless links to any designated sink node. Data is relayed through several intermediate nodes across a gateway towards the destination node like a wireless Ethernet.

2 Literature Survey

2.1 Routing Techniques

Souihli et al. [1] had proposed a novel a load balancing mechanism that could be applied in MANET using shortest path routing protocols. Distribution of maximum load is observed at the centre of the network, and accordingly, the proposed load balancing schemes drive the traffic or the observed load from the centre of the network. Based on the characteristics of routing protocol, the central node is designated as proactive or reactive. In reactive types, the nodes are characterized according to their centrality that is based on the size of their routing tables. In proactive types, the centrality of a node is fixed based on its multi-point relay selector list. The proposed load balancing schemes provide efficient load distribution, end-to-end delay and packet delivery fraction. The proactive feature in the proposed schemes effectively identifies the nodes that are congested and overloaded and relieves them. The authors had not taken into account of the performance of their schemes under non-uniform node distributions.

Protecting the privacy of the sink nodes in WSN is highly challenging. The sink nodes are highly vulnerable as they can easily fall prey to adversaries who can eavesdrop on the packets to identify its destination. The sink node privacy issue had been addressed by Long et al. [2] who had proposed a ring-based routing (RBR) technique. In the RBR technique, the authors had introduced the concept of multiple rings and multiple routing lines. Data is not directly transmitted to the sink node instead to the nearest routing ring. Data transmission takes place through routing rings that are relayed by further rings through routing lines till it reaches the destination. The count of anonymous sink nodes is kept equal to the number of network nodes. The proposed RBR technique is highly scalable and increases the network lifetime and accounts for high energy efficiency.

Lee et al. [3] had analysed the adhoc networks and had proposed the split multi-path routing (SMR) protocol. The proposed SMR protocol functions as on on-demand protocol that creates maximum number of disjoint routes. Each session of data transmission comprises of two routes, namely the shortest delay route and maximally disjoint shortest delay route. These maximum disjoint routes are designed with the idea of avoiding routes that may be congested to efficiently utilize the network resources. In adhoc networks, the presence of multiple paths helps in overcoming disconnected routes where source can choose any available route without the necessity of route recovery. The proposed protocol introduces end–to-end delay whenever routes are disconnected and consumes more energy during such occurrences.

Hu et al. [4] had proposed a technique that brings a balance between the quality of detecting the target and the lifetime of WSN. The authors had proposed an intelligent adjustable sensing frequency for mobile target detection based on the monitor quality optimization. In the proposed technique, the target is monitored using two schemes, namely target detection with sensing frequency K (TDSFK) and target detection with adjustable sensing frequency (TDASF). The former technique senses the frequency increase from 1 to K, and the latter technique adjusts the sensing frequency on nodes having residual energy. The two techniques are adaptable for networks containing static sinks and are not suited for networks with mobile sinks.

Zhang et al. [5] had proposed a dynamic sensing technique that addresses the routing issues for maximizing the utilization of rechargeable sensor networks. The authors had proposed a balanced efficient energy allocation scheme (BEAS) that manages the energy utilization in sensor nodes and makes the entire process as smooth as possible. In the proposed technique, the optimal sensing rate and routing control had been accounted through a distributed sensing rate and routing control (DSR2C) algorithm. The cost expended in managing the energy allocation and controlling the topology is very high in the proposed technique.

2.2 Cluster Formation Techniques

Li et al. [6] had analysed the WSN and proposed that resource efficiency and dependability of a trust system are required for securing data. Present trust systems are generating too much overhead and possess low dependability, hence not suitable for enforcing high security. The authors had proposed a lightweight and dependable trust system (LDTS) for WSNs that employ clustering algorithms. Energy preservation is brought in using a lightweight trust decision-making technique that operates based on identities of nodes in the WSN clusters. The effect of malicious nodes is negated, and system efficiency is improved by cancelling of feedback between the individual cluster members or cluster heads. Since huge data is forwarded by the cluster heads, a dependability-enhanced trust evaluating approach had been implemented at the cluster heads for cooperation purposes. It is huge improvement when compared to traditional techniques that fix weights subjectively. When compared with existing trust systems, the proposed LDTS generates less overhead and consumes less memory. The dependability-enhanced trust evaluating approach effectively detects and prevents malicious nodes and faulty cluster heads.

Naruephiphat et al. [7] had proposed an innovative clustering algorithm named limiting member node clustering (LmC) algorithm that limits the node members included under each cluster head based on a threshold value. A new cost function is used for selecting the cluster head by taking into account of battery level, energy consumption and its distance to the base station. The transmission range of base stations had been considered for improving the performance of clusters in WSN. The proposed approach provides efficient delivery ratio, increased network lifetime, low latency and less energy consumption when compared with other existing techniques.

2.3 Trust-Based Routing Techniques

Zhou et al. [8] had analysed the WSN based on trust and had proposed a trust behaviour collection technique that behaves like a watchdog. The watchdog transmits the data in multiple hops based on the location of the sensor nodes and the trustworthiness of the target nodes. The proposed technique calculates the trust of nodes and minimizes the cost of energy expended by the watchdog. The proposed technique reduces the life span of the network due to high energy consumption. Also consistent security is not always afforded.

Zhan et al. [9] had designed and implemented a robust trust-aware routing framework for WSNs named trust-aware routing framework (TARF) for securing the multi-hop routing in the dynamic WSN from adversaries. In the proposed technique, each node tracks the trustworthiness of its neighbours and accordingly selects any for transmitting its data. The proposed technique focuses on trustworthiness and energy efficiency. Protection is provided against the replay attacks. TARF is scalable and highly resilient, and the same is proved by comparing it with other existing trust techniques for large-scale WSNs.

Yu et al. [10] had reviewed the trust mechanisms and attacks taking place in the WSNs. The authors had categorized all attacks that take place based on trust in WSN. An intelligent behaviour attack model is implemented to identify inconsistencies in behaviour in the content domain. Various methodologies of trusting techniques had been analysed to provide proper emphasis on trust schemes in WSNs. The proposed approach makes use of Bayesian trust model, entropy trust model, fuzzy trust model, game theory trust model and subjective logic trust model. Behaviour attacks at MAC layer are successfully identified by the proposed approach. Also, efficient protection is not afforded against other security attacks like black hole attack, worm whole attack, selective forwarding and hello flood attack.

Danyang in et al. [11] had studied the critical attacks that could be launched on data transmission in WSNs due to limited energy resource and improper deployment of the sensor nodes. The authors had proposed a trust sensing-based secure routing mechanism (TSSRM) that is lightweight in nature and possessed the ability to thwart several simultaneous attacks. Performance analysis and evaluation of the proposed TSSRM had shown that it affords effective security against a host of attacks. Secure routing algorithms based on trust sensing routing protocols had been proposed for improving security and overcome common network attacks in the WSN environment. The proposed technique improves the reliability of data transmission in the network when compared to other existing trust-based techniques.

Maarouf et al. [12] had analysed the constrained nature and the prevailing insecurity in WSN and had proposed a trust-aware routing for wireless sensor networks (WSNs) named efficient monitoring procedure in a reputation system (EMPIRE). Reputation-based solutions had been suggested to enforce trust-aware routing where a node needs to continuously monitor its environment for detecting any misbehaviour events that are taking place. Given the resource scarcity present in the WSN, this seems to be a costly affair. The proposed EMPIRE technique is a probabilistic, distributed monitoring methodology that reduces the monitoring activities that are performed by any node and at the same time maintains the attack detecting capability to a satisfactory level. The authors had carried out the simulation using the Monte Carlo simulation technique.

WSNs are generally deployed in security-critical applications, and due to the inherent restrictions in sensor nodes and deployment environment, security can be easily compromised. Present techniques do not efficiently evaluate the trust among nodes and fail to establish energy-efficient routing to enforce security in the WSNs. In order to overcome these issues, energy-efficient clustering and trust-based secure routing scheme are necessary.

3 System Architecture

The proposed approach mainly focuses on energy-efficient clustering and trust-based Sybil attack detection scheme with secure routing in WSNs. The initial process of the secure routing is to form clusters based on location of the nodes and energy. A modified PSO-based clustering algorithm is implemented for cluster formation around the sink coverage area, a process that is initiated by the sink node. The trust and energy of the node calculation as well as Sybil node detection are done by using energy trust system (ETS). ETS consists of two levels of estimation such as CH level estimation and BS level estimation. In CH level estimation, CH receives a control packet from a CM and initiates the verification process. If the CM is legal energy and trust values are estimated based on successful, unsuccessful interaction and timing window, then accepts the packet. Else the CM is illegal that CM is declared as a Sybil node and then deletes the received packet. In BS level estimation, BS receives a packet from a CH and initiates the verification process. If the CH is legal energy and trust values are estimated based on successful, unsuccessful interaction and timing window, then accepts the packet. Else the CH is illegal, that CH is declared as a Sybil node and then deletes the received packet. BS sends the feedback packet via the trusted route to the source CM. Source node transfers the data packet via trusted route to the CH, and CH transfers the data to BS. If the data packet reaches the BS, the BS sends the feedback to its source node. The system architecture had been represented in Fig. 1.

Fig. 1

Energy-efficient clustering and trustable routing

3.1 Cluster Formation

Sensors that are in the vicinity of sink are mostly utilized for delivering data to the sink. Since they are constantly engaged in data transfers, their energy level gets drained up quickly than other nodes. This leads to the formation of hotspots at the sink surrounding area resulting in network isolation. This could be termed as hotspot or energy hole issue. The proposed modified PSO-based clustering algorithm improves the lifetime of the network by reducing the formation of hotspots.

In the modified PSO-based clustering, cluster formation is initiated by the sink node around its coverage area. An info-req-msg is transmitted by the sink to all nodes present in the coverage area. Whenever a message is received by the nodes around sink, they transmit the received message along with the info-reply-msg that contains the sensor-id, position, velocity and current residual energy. The sink node receives the information and updates itself.

Consider a problem space composed of N number of particles in the sink coverage area. The fitness function formulated deduces the particle that has the best value in the swarm and also identifies the best position of each particle periodically. The fitness function for the modified PSO-based clustering is calculated for each particle by equation given below:

$$f_{p} = a_{1} x_{1} + a_{2} x_{2} + a_{3} x_{3}$$

where a₁ and a₂ are weighing parameters that take value between 0 and 1 and a₃ = 1 − a₁ − a₂.

$$x_{1} = \mathop \sum \limits_{i = 1}^{n} \frac{{d\left( {\text{current particle member}} \right)_{i} }}{{c_{n} }}$$

$$x_{1} = \mathop \sum \limits_{i = 1}^{n} \frac{{E\left( {{\text{member}}} \right)_{i} }}{{E\left( {\text{current particle}} \right)}}$$

3.2 Energy Trust System

The proposed work focuses on eliminating Sybil attacks in WSN by developing a lightweight trust-based system that has the capability to carry out multi-level detection mechanism in clustered WSNs. Establishing trust detection system in a clustered topology inside WSN reduces the communication overhead and energy consumed and improves the network scalability and throughput factors. In a heterogeneous WSN with N sensors, there are three entities, namely a base station (BS), cluster heads (CHs) and cluster members (CMs).

In the proposed approach, each sensor node has a unique identity, and positions of every sensor including the BS and CHs are recorded. The sensor nodes are identified by the monitoring node (either BS or CH) based on the information they send that contains their ID, position and energy level along with the sensed data. There are two levels of detection in the proposed ETS, namely cluster head level detection and base station level detection.

3.2.1 Cluster Head Level Detection

Detection is initially carried out at the cluster head (CH) level. Clustering of sensor nodes provides effective topology control. Responsibility of nodes within a cluster is assigned to the respective CH. Whenever a CH receives a message from one of its sensors, it applies the ETS scheme, using verification and trust mechanisms to check the source of that message. It then forwards the data to the BS by performing the following:

• 1. Checking

  The cluster head verifies the ID and position of the sender. Once it confirms that the sender of the message is from its own cluster region, it initiates the next step, namely the trust calculation, else it drops the received message. By doing so, Sybil attacks with forged ID and position can be successfully thwarted.

• 2. Trust calculation

In this step, the worst-case scenario happening through Sybil attack where the attacker succeeds in impersonating the ID and position of legitimate node is checked. The trust factor T_ch,x is deduced as shown in the below equation:

$$T_{{{\text{ch}},x}} = - \sum {\frac{{S_{{{\text{ch}}x}} }}{{S_{{{\text{ch}},x}} + U_{{{\text{ch}},x}} }}} - \sum {\frac{1}{{\sqrt {U_{{{\text{ch}},x}} } }}}$$

where S_ch,x indicates the total number of successful interactions between CH with node x, and U_ch,x indicates the total number of unsuccessful interactions between CH with node x. If the deduced value is found to be more than 0.3, then the node x is regarded as a trusted node. On the contrary, if the deduced trust value is found to be less than or equal to 0.3, node x is regarded as a Sybil node.

3.2.2 Base Station Level Detection

Second level of detection is carried out at the base station level. In the proposed system, the base station BS is designated as the central command authority. Due to the formation of clusters in the network, the amount of data transmitted to the BS gets reduced. The BS tracks the working of CHs in the network. Whenever a BS receives a message from any CH, it applies the proposed ETS methodology as follows:

• 1. Checking

Upon receiving a message, the BS verifies the ID and position of the sender. When it ascertains that the sender is an authentic CH, it begins the trust calculation step, else the BS drops the message.

• 2. Trust Calculation

The trust value R_bs,ch is deduced by the BS as follows:

$$R_{{bs,{\text{ch}}}} = - \sum {\frac{{S_{{bs,{\text{ch}}}} }}{{S_{{bs,{\text{ch}}}} + U_{{bs,{\text{ch}}}} }}} - \sum {\frac{1}{{\sqrt {U_{{bs,{\text{ch}}}} } }}}$$

where S_bs,ch indicates the total number of successful interactions between BS with cluster head ch, and U_bs,ch indicates the total number of unsuccessful interactions between BS with cluster head ch. If the deduced trust value is found to be more than 0.3, then the cluster head ch is regarded as a trusted cluster node. On the contrary, if the deduced trust value is found to be less than or equal to 0.3, the cluster head ch is regarded as a Sybil node.

3.3 Data Transmission Phase

In the proposed algorithm, both single and multi-path routing are implemented for selecting a near optimal route. A near optimal route with minimum cost, less hop count and maximum residual energy is selected. When an activity happens, the source sensor node transmits data in the shortest path in its corresponding time slice. During its next subsequent time slice, it transmits the next data packet to an alternate neighbour present in its coverage area, regarding it as the best-case multi-path route to traverse towards the sink.

4 Implementation and Results

4.1 Cluster Formation Phase

The sensor nodes are simulated with the help of Network Simulator2. The modified PSO-based clustering algorithm implemented at the sink coverage area by the sink node to form clusters. Once clusters are created, the sink transmits the info-req-msg to the sensors present in its coverage area. Upon receiving the info-req-msg, the sensor nodes send their respective information through the info-reply-msg. This info-reply-msg contains their ID, position, velocity and residual energy. The sink node maintains and updates the received information. The modified PSO-algorithm employed in this work is shown in Algorithm 4.1.

Algorithm 4.1 Modified PSO-based clustering algorithm

• 1: Procedure modified PSO-based clustering ()

• 2: Begin

• 3: Population of N particles are initialized with random positions and velocities

• 4: If target fitness or maximum iteration is not attained

• 5: for each particle p in N do

• 6: Calculatefitnessvalue(f_p) of each particle

• 7: if f_p>f (pBest) then

• 8: pBest =f_p

• 9: endif

• 10: end for

• 11: gBest = max(pBestinP)

• 12: for each particle p in N do

• 13: Calculatevelocity

• 14: Calculateposition

• 15: end for

• 16: End while

• 17: End Modified PSO-based clustering

Figure 2 illustrates the deployment of nodes and network formation. The output of the cluster formation in the network is shown in Fig. 3.

Fig. 2

Network deployment

Fig. 3

Cluster formation

4.2 Energy Trustsystem

Every sensor nodes in the network including the cluster head CHs and base station BS are assigned unique ID and position values. The sensor nodes are identified by the monitoring node which could be either the CH or BS, based on the information they transmit that includes their ID, position, energy level and the actual sensed data. The proposed ETS has two levels of detection, namely cluster head level detection and base station level detection.

Upon receiving a message from any of its members, the cluster CH applies the ETS technique to ascertain the authenticity of the sender using the verification and trust mechanisms. The cluster head level detection algorithm employed in this work is shown in Algorithm 4.2 (Figs. 4 and 5).

Fig. 4

Fitness value calculation

Fig. 5

Cluster head level verification

Algorithm 4.2 Cluster head level detection algorithm

• 1: Input: Check whether the message was sent from a legitimate or sybil node.

• 2: Output: Identification of a sybil attack in WSN by applying the ETS.

• 3: Initialize the sensor nodes

• 4: CH receives a message from a CM

• 5: CH initializes verification (ID,position,energy) of the CM

• 6: if legal ID and position then

• 7: Calculate a trust

  $$R_{{bs,{\text{ch}}}} = - \sum {\frac{{S_{{bs,{\text{ch}}}} }}{{S_{{bs,{\text{ch}}}} + U_{{bs,{\text{ch}}}} }}} - \sum {\frac{1}{{\sqrt {U_{{bs,{\text{ch}}}} } }}}$$

• 8: if T >0.3then

• 9: Trusted node and send the message toBS

• 10: endif

• 11: else

• 12: Delete received message from CM(sybilnode)

• 13: endif

In a similar manner, the BS, upon receiving a message from any of the cluster heads CHs, applies the ETS technique to ascertain the authenticity of the sender using the verification and trust mechanisms. The base station level detection algorithm employed in this work is shown in Algorithm 4.3 (Figs. 6, 7 and 8).

Fig. 6

Base station level verification

Fig. 7

Sybil attacker node detection

Fig. 8

Data transmission to BS

Algorithm 4.3 Base station level detection algorithm

• 1: Input: Check whether the message was sent from a legitimate or sybil node.

• 2: Output: Identification of a sybil attack in WSN by applying the ETS.

• 3: Initialize the sensor nodes

• 4: BS receives a message from a CH

• 5: BS initializes verification (ID,position,energy) of the CH

• 6: if legal ID and position then

• 7: Calculate a trust

  $$R_{bs,ch} = - \sum \frac{{s_{bs.ch} }}{{s_{bs,ch} + U_{bs,ch} }} - \sum \frac{1}{{\sqrt {U_{bs,ch} } }}$$

• 8: if T >0.3then

• 9: Trusted node and accepts themessage

• 10: endif

• 11: else

• 12: Delete received message from Ch(sybilnode)

• 13: end

5 Conclusion

In this paper, data is transferred over multiple nodes in a secured manner. The clustering algorithm is implemented to form cluster nodes. ETS maintains unique ID for each node, and fitness level is calculated using cluster level head detection algorithm. Sybil attacker node is verified before data transmission to BS. Base station level detection reduces attackers. Algorithm like modified PSO cluster algorithm, cluster level head detection and BS level algorithm are implemented to reduce the attackers’ entry during data transmission from node to node.