Improvised Energy Efficient Routing Protocol based on Ant Colony Optimization (ACO) for Wireless Sensor Networks

Table of Contents

Declaration

Certificate

Acknowledgments

Abstract

Table of Contents

List of Figures

List of Tables xiii

Acronyms xv

Chapter – 1 : Introduction
1.1 Sensor Networks- Evolution and Introduction
1.2 Model of Wireless Sensor Network
1.3 Wireless Sensor Networks- Design Principles and Challenges
1.4 Wireless Sensor Networks – Types
1.5 Wireless Sensor Networks- Classifications
1.6 Wireless Sensor Network Architecture: Protocol Stack
1.7 Routing in Wireless Sensor Networks
1.7.1 Challenges connected to Routing in Wireless Sensor Networks
1.7.2 Classifications of Routing Algorithms/Protocols
1.8 Swarm and Swarm Intelligence (SI)
1.9 Ant Colony Optimization (ACO)
1.9.1 Introduction
1.9.2 Ants in Nature
1.9.3 Ants Stigmergic behavior
1.9.4 Real Ants v/s. Artificial Ants
1.9.5 Ant Colony Optimization Metaheuristic
1.9.6 Mathematical Model of Ant Colony Optimization
1.9.7 Components of Ant Colony Optimization (ACO)
1.9.8 Ant Colony Optimization Algorithms
1.9.8.1 Ant System Algorithm
1.9.8.2 Ant Colony System (ACS)
1.9.8.3 MAX-MIN Ant System
1.9.8.4 Ant Lion Optimizer
1.9.9 Ant Colony Optimization- Working and Algorithm
1.10 Suitability of Ant Colony Optimization (ACO) based approach for Developing Energy Efficient Routing Protocols for Wireless Sensor Networks
1.11 ACO Based Routing Protocols for Wireless Sensor Networks
1.11.1 Sensor Driven Cost-Aware Ant Routing (SC)
1.11.2 Energy Efficient Ant Based Routing (EEABR)
1.11.3 Flooded Forward Ant Routing (FF)
1.11.4 Flooded Piggyback Ant Routing (FP)
1.11.5 Energy-Delay Ant Based (E-D Ants)
1.11.6 Ant Colony Based Reinforcement Learning Algorithm (AR and IAR)
1.11.7 Basic Ant Based Routing (BABR) for Wireless Sensor Networks (WSN)
1.11.8 Ant Based Quality of Service Routing (ACO-QoSR)
1.11.9 Ant Colony Optimization based Location-aware Routing (ACLR)
1.12 Energy Efficient Routing Protocols based on Ant Colony Optimization for Wireless Sensor Networks
1.12.1 Ant Chain Protocol
1.12.2 Ant Aggregation
1.12.3 Pheromone Based Energy Aware Directed Diffusion (PEADD)
1.12.4 Ant Colony Multicast Trees (ACMT)
1.12.5 Improvised Ant Colony Routing (IACR)
1.12.6 ACO Router Chip
1.12.7 Energy Balanced Ant Based Routing Protocol (EBAB)
1.12.8 Adaptive Clustering for Energy Efficient WSN based on ACO (ACO-C)
1.12.9 Ant Colony Clustering Algorithm (ACALEACH)
1.12.10 Ant Colony Optimization based- Energy-Aware Multipath Routing Algorithm (ACO-EAMRA)
1.12.11 Energy Efficient ACO Based QoS Routing (EAQR)
1.12.12 Comprehensive Routing Protocol (CRP)
1.13 Organization of Thesis
Summary

Chapter – 2 : Literature Review

Chapter – 3 : Research Methodology
3.1 Motivation
3.2 Research Problem
3.3 Research Objectives
3.4 Research Methodology
3.5 Research Contributions
3.6 Scope of Research
3.7 Research Gaps Identified

Chapter – 4 : IEEMARP: Improvised Energy Efficient Multipath Ant Colony Optimization based Routing Protocol for Sensor Networks
4.1 Problem Definition and Background
4.2 Protocol Design Choices
4.2.1 Energy Efficiency
4.2.2 Reliability
4.2.3 Dynamic Network and Scalability
4.2.4 Throughput and Routing Overhead
4.3 Assumptions
4.4 IEEMARP Protocol- Operation
4.4.1 Neighborhood Discovery via Link Knowledge
4.4.2 Forwarding of Packets / Fault Localization
4.4.3 Reliable End-to-End Communication from Source to Destination
4.5 IEEMARP Routing Protocol- Properties
4.6 IEEMARP Protocol- Algorithm
4.7 IEEMARP Routing Protocol- Algorithm
Summary

Chapter – 5 : Simulation and Performance Analysis of IEEMARP Routing Protocol
5.1 Introduction to NS-2 Simulator
5.2 Performance Metrics
5.3 Simulation and Performance Comparison of Basic Ant Colony Optimization (ACO) Routing Protocol with AODV, DSR and DSDV Routing Protocols for Wireless Sensor Networks
5.3.1 Flowchart of Simple Ant Net Based Routing
5.3.2 Simulation Parameters
5.3.3 Simulation Scenarios
5.3.4 Simulation Results
5.4 Simulation and Performance Comparison of Basic Ant Colony Optimization based Routing Protocols: ACEAMR, AntChain, EMCBR and IACR
5.4.1 Simulation Parameters
5.4.2 Simulation Results
5.4.3 Overall Analysis and Best Protocol Suitability
5.5 Simulation and Performance Comparison of Proposed Routing Protocol
5.5.1 Simulation Parameters
5.5.2 Simulation Scenarios and IEEMARP Routing Protocol working
5.5.3 Performance Results of IEEMARP Routing Protocol with ACEAMR, AntChain, EMCBR and IACR routing protocols on performance metrics
5.5.4 Performance Comparison of IEEMARP routing protocol with Traditional WSN routing protocols: DSR, DSDV and Basic ACO
Summary

Conclusion and Future Scope

References

List of Figures

1.1 Wireless Sensor Network

1.2 Sensor Node components

1.3 Types of Wireless Sensor Networks

1.4 Terrestrial WSN

1.5 Underwater WSN

1.6 Underground WSN

1.7 Mobile WSN

1.8 Multimedia WSN

1.9 Protocol Stack of Wireless Sensor Networks

1.10 Classifications of Routing Algorithms

1.11 Ants stigmergic behavior

1.12 Ant Colony Optimization

3.1 Research Methodology Undertaken

4.1 IEEMARP Routing Protocol Operation

5.1 Basic Structure of NS-2 Simulation

5.2 Flowchart demonstrating Ant Based Routing Algorithm

5.3 Deployment of 100 Nodes creating Wireless Sensor Network Scenario

5.4 Base Station location

5.5 Route Discovery

5.6 Transmission of TCP Packet

5.7 Generation of Acknowledgement Packet

5.8 Control Packet Overhead

5.9 Handling of Route Failure by Ant Colony Optimization Algorithm

5.10 Packet Delivery Ratio comparing ACO with DSR, DSDV and AODV routing protocols.

5.11 Throughput comparing ACO with DSR, DSDV and AODV routing protocols

5.12 Routing Overhead reduced by ACO as compared to DSR, DSDV and AODV routing protocols

5.13 End to End significantly reduced by ACO as compared to DSR, DSDV and AODV routing protocols

5.14 Energy Consumption by Node utilized via ACO protocol as compared to DSR, DSDV and AODV routing protocols

5.15 Packet Delivery Ratio of ACEAMR, AntChain, EMCBR and IACR

5.16 Comparison of Routing Protocols considering Throughput parameters

5.17 Comparison of Routing Protocols on basis of Probability Routing Overhead

5.18 Energy Consumption comparison of Sensor Nodes on basis of different routing protocols in sensor networks

5.19 Comparison of Routing Protocols on basis of End-to-End Delay

5.20 IEEMARP Simulation Start Scenario with Neighbouring Nodes Routing Table update using ACO routing protocol.

5.21 Route Discovery by IEEMARP Routing Protocol

5.22 Packet Transmission by Sensor Node to Sink Node via TCP Protocol for reliable end-to-end communication.

5.23 ACK Packet transmitted by Base Station (Node 0) to Sensor node confirming the acknowledgement of the received packet

5.24 Packet Dropped due to Routing Overhead

5.25 Link Status between Source Node to Sink Node.

5.26 Packet Delivery Ratio- Performance Metric Comparison

5.27 IEEMARP throughput comparison with other routing protocols

5.28 Routing Overhead based Performance comparison of IEEMARP routing protocol with other routing protocols.

5.29 Energy Consumption comparison of Routing Protocols with IEEMARP routing protocol

5.30 End-to-End delay based performance comparison of IEEMARP routing protocol with WSN based other routing protocols

List of Tables

1.1 Sensor Node Evolution

1.2 Real Ants V/s Artificial Ants.

5.1 Outlines the Simulation Parameters- Basic ACO Routing Protocol

5.2 Packet Delivery Ratio of ACO v/s DSDV, AODV and DSR Routing Protocols

5.3 Throughput analysis of ACO v/s AODV, DSDV and DSR routing protocols

5.4 Routing Overhead based results and comparison of ACO with DSDV, AODV and DSR routing Protocols.

5.5 End to End delay based results and comparison of ACO with DSDV, AODV and DSR routing Protocols.

5.6 Energy Consumption by Nodes in Path Selection and Data transmission between sender and receiver node.

5.7 Simulation Parameters for Performance Comparison of ACEAMR, IACR, EMCBR and AntChain Routing Protocol.

5.8 Data Analysis of Routing Protocols (ACEAMR, AntChain, EMCBR and IACR) on basis of Packet Delivery Ratio

5.9 Data Analysis of Routing Protocols (ACEAMR, AntChain, EMCBR and IACR) on basis of Throughput

5.10 Data Analysis of Routing Protocols (ACEAMR, AntChain, EMCBR and IACR) on basis of Routing Overhead

5.11 Data Analysis of Routing Protocols (ACEAMR, AntChain, EMCBR and IACR) on basis of Energy Consumption

5.12 Data Analysis of Routing Protocols (ACEAMR, AntChain, EMCBR and IACR) on basis of End-to-End Delay

5.13 Overall Analysis of Best Protocol Suitability among ACEAMRA, EMCBR, IACR and AntChain Routing Protocol

5.14 Simulation Parameters for Simulating IEEMARP Routing Protocol and Comparison with ACEAMRA, AntChain, IACR and EMCBR routing protocols

5.15 Performance comparison of Routing Protocols- ACEAMR, AntChain, EMCBR, IACR and IEEMARP on basis of Packet Delivery Ratio

5.16 Performance comparison of Routing Protocols- ACEAMR, AntChain, EMCBR, IACR and IEEMARP on basis of Throughput

5.17 Performance comparison of Routing Protocols- ACEAMR, AntChain, EMCBR, IACR and IEEMARP on basis of Routing Overhead

5.18 Performance comparison of Routing Protocols- ACEAMR, AntChain, EMCBR, IACR and IEEMARP on basis of Energy Consumption

5.19 Performance comparison of Routing Protocols- ACEAMR, AntChain, EMCBR, IACR and IEEMARP on basis of End-to-End Delay

5.20 Performance Comparison of IEEMARP routing protocol with DSDV, DSR and Basic ACO routing protocols on varied performance parameters

Acronyms

Abbildung in dieser Leseprobe nicht enthalten

DECLARATION

I hereby affirm that the work presented in the Thesis entitled “Improvised Energy Efficient Routing Protocol based on Ant Colony Optimization (ACO) for Wireless Sensor Networks” submitted for the Ph.D Degree is exclusively my own original work and verified by Plagiarism. It does not contain any work for which a Degree has been awarded by any other University.

Date: Signature of the Student

Signature of Guide

CERTIFICATE

It is certified that the Thesis entitled “Improvised Energy Efficient Routing Protocol based on Ant Colony Optimization (ACO) for Wireless Sensor Networks” is the bonafide research work carried out by Anand Nayyar, a Research Scholar of Ph.D (Computer Science), Desh Bhagat University, Mandi Gobindgarh, during the year 2017, for partial fulfilment of the requirements for the award of the Degree of Doctor of Philosophy and that the Thesis has not being formed on the basis for the award previously of any degree, diploma, associateship, fellowship or any other similar title.

Date: Signature of the Guide

Signature of External Expert

Signature of the Dean Research

Acknowledgement

It is my honour to express my deep gratitude to people who made this challenge possible for me. I would like to thank my Supervisor Dr. Rajeshwar Singh for giving me the opportunity to work under him. He offered me such a challenging topic for my thesis and with his strong support and constant guidance; I am finally able to achieve my goals. He did not only guide me in the course of this thesis, but also provided me an opportunity to be benefited from his vast knowledge. His enormous knowledge about wireless routing, was a source of immense help and it is his time and guidance that made this thesis better.

Secondly, I am thankful to Dr. Sidhu Mam, Incharge of Research & Development Cell, Desh Bhagat University to provide me great support and helped me to overcome many difficulties in my research work.

I am indebted to my parents, Mr. Sunil Kumar Nayyar and Mrs. Meenakshi Nayyar, my sister Dr. Sanchi Sharma and my best friend Er. Vikram Puri, for everything I own now. It is their prayers and support that gave me the courage and ability to fulfill my goals.

(Anand Nayyar)

Abstract

Routing and Energy Efficiency is regarded as highly challenging area of Sensor networks. Significant advancements in Wireless Sensor Networks (WSNs) opens doors for wide implementation in real-time applications like Industrial Monitoring, Smart Cities development, Underwater monitoring operations, tracking objects and many more. Energy Efficient routing is regarded as the most challenging task. Sensor networks mostly operate in complex and dynamic environments and routing becomes tedious task to maintain as the network size increases. Lots of routing protocols- Reactive, Proactive and Hybrid are proposed by researchers but every protocol faces some limitations in terms of energy, routing, packet delivery ratio and security. Therefore, to overcome all the routing issues, the trend has shifted to Biological based Algorithms like Swarm Intelligence based techniques. Ant Colony Optimization based routing protocols have demonstrated exceptional results in terms of performance when applied to WSN routing.

This thesis outlines routing protocols in sensor networks, highlight the concept of Swarm Intelligence and presents various Ant Colony Optimization based routing protocols for sensor networks. In addition to this, we present Ant Colony based Energy Efficient routing protocol (IEEMARP = Improvised Energy Efficient Multipath Ant Based Routing Protocol) for sensor networks. The proposed protocol takes into consideration various performance metrics like Packet Delivery Ratio, Throughput, Energy Efficiency, Routing Overhead and End-to-End delay. Proposed protocol is simulated and tested using NS-2.35 simulator. Simulation based results stated that IEEMARP routing protocol is overall 16% more efficient in terms of Packet delivery ratio, Energy Efficiency, Throughput, Routing Overhead and End-to-End delay as compared to other ACO based routing protocols. In addition to this, IEEMARP is highly reliable protocol to ensure timely delivery with acknowledgement packet exchange between source node to sink node and vice versa and also combats the issue of congestion and packet dropping to large extent.

Chapter – 1 Introduction

This chapter outlines the concept of Wireless Sensor Networks- Evolution, Types, Design principles and challenges, classifications and protocol stack in addition to various Adaptive and Nonadaptive routing protocols for sensor networks and also highlights the comparison among protocols on varied performance parameters. The chapter also covers comprehensive details regarding Swarm Intelligence, Ant Colony Optimization and also enlists various ACO based Energy Efficient protocols for performing routing activity in sensor networks.

Wireless Sensor Networks

Wireless Sensor Networks comprise of few to thousands of sensor nodes with sophisticated capabilities to interact with environment by sensing or controlling physical parameter with power of collaborating among each other to perform the tasks [1]. According to SmartDust program of DARPA, Wireless Sensor Network is [1]:

“A Sensor Network is a deployment of massive numbers of small, inexpensive, self-powered devices that can sense, compute and communicate with other devices for the purpose of gathering local information to make global decisions about a physical environment”.

1.1 Sensor Networks- Evolution and Introduction

The initial deployment of Sensor Network was done during Cold War by United States of America [4] when a large network comprising of acoustic sensors were deployed at strategic locations beneath the ocean to track Soviet Union submarines. The system of Acoustic sensors was defined as Sound Surveillance System (SOSUS). The sensor network deployed was not wireless all the sensors are connected via wired links and doesn’t have any sort of energy constraints.

Serious research on Sensor networks was started in late 1980s by Defense Advanced Projects Agency (DARPA) via Distributed Sensor Networks (DSN) program. DSN program comprised of research surrounding acoustic sensors communication, advanced techniques regarding processing, algorithms and distributed software.

Table 1.1. Sensor Node Evolution

Abbildung in dieser Leseprobe nicht enthalten

With the advancements in area of Wireless communications, Digital Electronics and especially MEMS (Micro Electromechanical Systems), the development of smart sensors in terms of low cost, less energy consumption with multifunctional sensing has become possible. These smart sensors are extremely small size and have the capability of sensing, data processing and communicating with different sensor networks via Radio Frequency (RF) channel. Wireless Sensor Networks [2, 3] comprise of smart sensor nodes which are low power devices equipped with multi-functional sensors, processor, memory, power supply unit, a radio and an actuator. Different sorts of mechanical, thermal, environmental, magnetic, chemical and optical sensors are connected to sensor nodes to sense the data from real-time environment. Wireless sensor networks, in recent times, have seen great potential for many application areas like Military, Environmental monitoring, Medical, Space technology, Robotics, Industrial production and many more. [3,4,5].

Wireless Sensor Networks have very less or no infrastructure [4]. It comprises of limited to tons of sensor nodes working cooperatively for monitoring a particular region and obtaining the live data from the environment. WSN’s are of two types: Structured and Unstructured. In Structured WSN, the entire sensor nodes are deployed after proper planning. In Unstructured WSN, the sensor nodes are deployed in ad hoc manner in the environment, and after deployment, sensor nodes operate autonomously to perform the task of monitoring, sensing and reporting data.

Wireless Sensor Networks, when compared to traditional networks, have its own limitations and constraints in terms of design and resources like limited energy, limited amount of energy, less processing capability, small communication range, less QoS and data storage capability. Research in WSNs is basically done in order to cope up with these challenges and to bring up sophisticated and advanced sensor nodes with new design via improvised routing protocols, new applications deployment and new algorithms to make sensor nodes less vulnerable to different types of attacks.

The following are the basic features of sensor networks [7, 8]:

a. Capability for self-organizing and multi-hop routing.
b. Dense deployment and intelligent cooperating communication capabilities with neighboring nodes.
c. Dynamic nature of topology change in case of node failures or fading.
d. Short range broadcast communication via radio frequency (RF).
e. Limitations in terms of memory, computations and transmission power.

The vast growth of wireless communication not only alleviates the dependency on traditional wired networks, but also increases the suitability of mobile communication and enhances its computing power. In WSN, each sensor node acts as a router with ability of sensing. Although, the sensor nodes are highly mobile operating in dynamic changing topology, the protocol handling all the operation should be able to handle the rapid topology changes [9].

The sensor nodes are equipped with data processing communication capabilities. Sensor nodes collect the data via sensors integrated and transmits the data back to sink node (Base Node) via Radio frequency (RF) directly or via Gateway node. Sensor Networks are usually small and inexpensive, so tons of nodes are deployed in random manner considering various limitations of energy, memory, computational speed and bandwidth. Every sensor utilizes tons of energy while receiving and transmitting data [10].

Extensive research is being undertaken by researchers to develop and propose energy efficient protocols cum algorithms for WSN to enhance the overall lifetime of network. In most of applications, sensor nodes are really constrained in terms of energy and bandwidth. Therefore, novel techniques to effectively utilize power and enhance bandwidth is required. Such constraints in WSN poses lots of challenges for deployment in real world applications [5] [6].

1.2 Model of Wireless Sensor Network

Like traditional ad hoc networks, WSN networks are limited in terms of resources, excessively prone to failures, so tons of sensor nodes are deployed in real time environment as compared to ad hoc networks. The topology of sensor networks is highly dynamic and changes continuously.

The following are the major components of sensor networks:

- Sensor deployment field: A sensor deployment field comprise of area in which nodes are deployed for real time sensing.
- Sensor nodes: Sensor nodes perform the task of sensing, collecting, processing and routing the data back to sink node via path nodes.
- Sink node: A sink node (also known as Base Node) perform the task of receiving, processing and storing the data received from deployed sensor nodes. They perform the task of reducing the total number of messages to be sent to maintain the energy level of nodes and overall network lifetime. Sink nodes are also termed as Data Aggregation nodes.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.1. Wireless Sensor Network

1.3 Wireless Sensor Networks- Design Principles and Challenges

It is clear from the above section that WSNs are application-specific, but even with wider applications deployment scope and technical advantages, there are some challenges of wireless sensor networks in effective design.

- Effective topology control: Most of applications where sensor nodes are deployed remain static in the monitoring area and this is an important factor which distinguishes sensor networks from other ad hoc networks. Sensor networks require effective topology management when deployed to efficiently monitor the area. With issues of wireless interference, power and node damage, topology control seems to be indispensable for sensor nodes to operate in dynamic environment.
- Sensor lifetime: Sensor nodes have limited energy and cannot remain operational for large period of time. The chief source providing power to sensor nodes is either AA or AAA battery cells and sometimes solar power. Most of the applications require WSNs to remain operational for longer period. Batteries with rechargeable capabilities can be a great support but requires consistent attention and continuous replacement which can boost up the cost of sensor networks operations. So, energy efficiency improvement to enhance lifespan of WSNs has become the primary challenge for researchers across the world to overcome and even energy efficient routing protocols are proposed for improving sensor networks lifetime.
- Cost: In order to make more real-time applications operational with sensor technology, the cost is the chief concern. The price of each sensor should be less than a dollar or ($1). The other components which are required for sensor node: power unit, sensing unit, processor and transceiver can even increase the cost.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.2. Sensor Node components

- Fault Tolerance: Sensor nodes are prone to failure via hardware or software crash or sometimes via battery drain. Sensor network should be deployed with additional nodes and effective topology control strategy to make WSN network operate successfully regardless of node failures.
- Standardization: Another issue directing the eyes of researchers for solutions in sensor networks is standardization. The design goal of WSNs is [6]: “The Goal of WSN engineers is to develop a cost-effective standards-based wireless networking solution that supports low-to-medium data rates, has low power consumption and guarantees security and reliability.” Varied standards are implemented for WSN like IEEE 802.15.4/ZigBee for indoor conditions and IEEE 802.16/WiMAX for external environments. Standardizations is highly required in routing protocols of WSN as well as other areas of WSN like cross-layer, middleware’s, operating systems, protocol stack etc.
- MAC Layer Issues: MAC layer has direct impact on power utilization in terms of collision, packet overheead and idle listening. Power saving forward error control technique is very hard to implement due to high computing requirements, so in turn long data packets transmission is not possible in WSN.
- Quality of Service (QoS): As WSN network works for real time and critical applications, it is hard to maintain QoS due to rapidly changing topology and routing information state which is consistently changing.
- Security: Security is the key challenge issue in WSN. In sensor networks, it is utmost necessary for each sensor node and the base station to have the ability to verify that the data received is actually sent by trusted sender not any outside untrusted party. A false data can hamper the entire quality functioning of the network. Different sorts of threats in sensor networks are spoofing and altering the routing information and various active and passive attacks like Hello Flood Attack, Jelly Fish Attack, Sinkhole, Blackhole, Gray hole etc. in turn affecting the entire WSN network in terms of performance.
- Limited Memory and Storage Space: A sensor is tiny device with limited amount of memory and storage space for code. In order to design efficient security mechanism, it is necessary to limit the code size.

1.4 Wireless Sensor Networks – Types

Depending on the monitoring environment, the sensor nodes forming sensor networks can be deployed underwater, underground, land or even space. The following are the five major types of WSN network:

a. Terrestrial WSNs
b. Underwater WSNs
c. Underground WSNs
d. Mobile WSNs
e. Multimedia WSNs

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.3. Types of Wireless Sensor Networks

a. Terrestrial WSNs: In terrestrial WSNs, thousands of sensor nodes are deployed either in ad hoc manner or pre-planned manner and are efficient to communicate with base stations. Structured mode takes into consideration optimal placement, grid placement or 2D/3D placement models whereas in unstructured mode, the nodes are installed in random fashion over target area. Energy is the primary issue with terrestrial WSNs and energy retention can be done via low duty cycle operations, delay minimization and energy efficient routing protocols.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.4. Terrestrial WSN

b) Underwater WSNs : Underwater WSNs comprise of sensor nodes and sensor-oriented vehicles to uniformly operate underwater. Autonomous underwater vehicles are deployed for capturing sensed data from sensor nodes. The chief issues surrounding underwater WSNs are long propagation delay, quality of service, energy and sensor failures due to underwater obstacles.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.5. Underwater WSN

c) Underground WSNs : As compared to terrestrial WSNs, underground WSNs requires more cost in terms of deployment, maintenance and planning. Underground WSNs are deployed for monitoring underground conditions and communicate back to sink nodes above the ground. Sensor nodes are really difficult to charge and maintain, as nodes operate under the ground. Other issues surrounding underground WSNs are QoS wireless communications as signal loss and attenuation always occurs.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.6. Underground WSN

d) Mobile WSNs : Mobile WSNs operate in physical environment for capturing real time data and are more versatile as compared to static sensor networks. Mobile WSNs are better in terms of area coverage, QoS, energy efficiency, better channel capacity etc.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.7. Mobile WSN

e) Multimedia WSNs : Multimedia WSNs perform the task of tracking and monitoring of events like imaging, audio, video etc. They are low cost sensor networks integrated with microphones and cameras and connect with other nodes in network via wireless communication for data compression, retrieval and correlation.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.8. Multimedia WSN

1.5 Wireless Sensor Networks- Classifications

WSNs are classified into the following different categories:

- Static and Mobile Network: WSN network can be static or mobile. In static sensor network, all sensor nodes are static without any movement. Static sensors can be deployed in Environmental monitoring or surveillance. Mobile Sensor Network are more versatile and can be deployed in any scenario and cope with rapid topology changes. A Wireless Biosensor network for monitoring animals is Mobile Sensor Network.
- Deterministic and Nondeterministic Network: In Deterministic Sensor Network, the positions of sensor nodes are pre-planned and are fixed once deployed. It is very challenging to deploy sensor nodes in pre-planned manner because of the harsh or hostile environments. Nondeterministic sensor networks are more scalable and flexible, but require higher control complexity.
- Static-Sink and Mobile-Sink Network: In a static-sink network, the sink is static with a fixed position located close to or inside a sensing region. A static sink makes the network easy to control and administer, but it would cause a hotspot effect resulting in that sensor nodes close to data sink would die early and would interrupt normal network operation. In a mobile-sink network, the sink moves around the network to collect data from sensor nodes.
- Single-Hop and Multi-Hop Network: In single-hop network, all sensor nodes transmit their sensed data directly to the sink node, which makes easy implementation of network control. This in turn, requires long range wireless communication which becomes costly in terms of energy and hardware and if the overall network size increases, energy will reduce and collisions will occur. In a Multi-Hop network, sensor nodes transmit their sensed data to the sink via intermediate nodes. Intermediate node perform the task of routing to forward the sensed data back to sink node.
- Self-Reconfigurable and Non-Self-Configurable Network: In a non-self-configurable network, sensor nodes have no capability to organize themselves and rely on central controller to control each sensor node and collect information. In self-reconfigurable network, sensor nodes are able to organize autonomously and maintain the connectivity and path for transmission of data.
- Homogenous and Heterogeneous Network: In a homogeneous network, all sensor nodes have same capabilities in terms of energy, computation and storage. In Heterogeneous network, sensor nodes are somewhat complicated as nodes are equipped with more processing and communication capabilities as normal nodes. Heterogeneous networks are better in terms of energy and overall life span.

1.6 Wireless Sensor Network Architecture: Protocol Stack

The protocol stack used by sensor nodes to communicate with base station is shown in figure 2.9. According to Akyildiz [2], the protocol stack of WSN is almost like traditional network protocol stack with multiple layers: Application, Transport, Network, Data link, Physical layer, Power management plane, mobility management plane and task management plane. [11]

The primary responsibilities of physical layer are frequency selection, carrier frequency generation, signal detection, modulation and data encryption.

Data link layer performs the tasks of data streams multiplexing, data frame detection, medium access and error control.

Network layer is responsible for routing the information i.e. calculating the most efficient path of data transmission from source to destination. Network layer design in WSNs also consider energy efficiency, data-centric communication, data aggregation etc.

Transport layer performs the task of data flow maintenance especially when data captured by sensor nodes is to be accessed via Internet or external communication networks.

The application layer does the task of presenting all the information to specific application and forwarding requests from application layer to lower layers in protocol stack. The software in application layer depends on sensor application.

The power management plane is mainly responsible for minimizing power consumption in sensor nodes and waking up only those nodes required for packet transmission.

The mobility management plane detects and registers movement of nodes to maintain the route of sender node to sink node.

The task management plane balances and schedules the sensing tasks to the sensing field and only specific nodes are assigned the sensing tasks and rest other nodes can perform other tasks like routing and data aggregation.

A network routing protocol for wireless sensor networks should be able to overcome all the necessary limitations and back points like Bandwidth, energy, electromagnetic wave propagation, congestion, collision and dynamic topology mobility.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.9. Protocol Stack of Wireless Sensor Networks

1.7 Routing in Wireless Sensor Networks

In general terms, Routing is regarded as process of discovering the path and transmission of data between source to sink node. In Wireless Sensor Networks, data routing is performed at network layer.

Routing in WSNs is regarded as highly challenging task due to following inherent characteristics which distinguishes WSNs with other types of wireless networks like Mobile Adhoc Networks (MANETS), Cellular or Home based Wi-Fi or WiMAX communications: [12, 13, 14]

- First, due to large number of sensor nodes deployment in real-world, which becomes somewhat hard to design a global addressing scheme for every node involved in sensor network as the overhead of unique ID maintenance is high.
- Sensor nodes are deployed in ad hoc manner so nodes have to work via self-organization, but with changing environmental conditions and limited energy of nodes with dynamic changing topology, this becomes really challenging.
- Sensor nodes have limited energy, storage and processing capabilities. So, careful resource management is required.
- Sensor applications varies from conditions to conditions. In some conditions, sensor nodes remain stationary but in some applications, sensor nodes may be allowed to move and change location.
- Position of sensor nodes is very important as data collection is normally based on location. But currently, it is not practically possible to integrate GPS (Global Positioning System) in sensor nodes. Methods based on triangulation facilitates sensor nodes to approximate their positions via radio signals to few points.
- Lastly, the data collected by sensors deployed in WSNs are of similar nature, which leads to high probability of data redundancy. Redundancy needs to be tacked by routing protocols to improvise energy and bandwidth.

Considering these above characteristics, the routing protocol must be simple, robust, energy efficient to maintain overall efficiency in network.

1.7.1 Challenges connected to Routing in Wireless Sensor Networks

Considering different real-time application scenarios, architectures and goals, Wireless sensor networks face different routing challenges and the performance of routing protocol entirely depends on architectural model.

The following points highlight the various challenges connected to routing in WSN [1, 5, 6, 12]:

- Deployment of Sensor Nodes: Sensor nodes deployment entirely depends on applications and have straight effect on protocol performance. The deployment can be either deterministic or self-organizing. In deterministic deployments, the nodes are installed as per plans and routing is performed via pre-determined paths. But in case of self-organizing, the nodes are installed in random manner. The position of sink node or cluster head is highly important to maintain energy efficiency and performance in network.
- Network Dynamic: Depending on applications, sensor nodes remain stationary but sometimes sensor nodes change the position and in that case topology become dynamic. Route stability is highly important to conserve energy and maintain overall QoS in network.
- Energy considerations: The most important factor to consider for setting up the route between source to destination is Energy Efficiency. As the transmission power of wireless radio is directly proportional to distance squared or high order in lieu of obstacles, multi-hop routing will be beneficial in terms of energy efficiency because of effective topology management and medium access control.
- Data delivery models: Data delivery models to sink node can be continuous, event-driven, query-driven or hybrid and all depends on sensor application operation. In continuous delivery model, every sensor in network sends data at periodic intervals. In event-driven and query-driven models, data transmission only happens on specific event triggering. In case of hybrid data delivery model, it makes use of combination of continuous, event-driven and query-driven data delivery models. The efficiency of routing protocol highly depends on selecting the effective data delivery model to utilize less energy and provide QoS in overall network.
- Data Aggregation: Sensor nodes generate same type of data which can lead to redundancy. It is regarded as effective collaboration of sensed from varied sources via using functions like suppression (Duplicates elimination), min, max and average. Routing protocols should carefully perform data aggregation to maintain overall transmission speed.

1.7.2 Classifications of Routing Algorithms/Protocols

Considering various issues and challenges of routing in sensor communications, various novel algorithms/protocols are proposed to for efficient routing in sensor networks. Figure 2.10 demonstrates the types of routing algorithms. Routing algorithms can be classified into following two major categories:

1) Adaptive Algorithm

2) Nonadapative Algorithm

Nonadaptive algorithms (or Static Algorithms) don’t adapt themselves to any sorts of changes in overall network.

Adaptive algorithms (or Dynamic Algorithms) change according to the topology and traffic load in overall network.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.10. Classifications of Routing Algorithms

Nonadaptive Routing Algorithms

Nonadaptive routing algorithms don’t take routing decision on basis of measurements and estimates of current traffic and topology. The routing path from node to node is determined in advanced, off-line and downloaded to routers when booting of network is performed. Non-adaptive routing is also known as static routing. In terms of static routing, any change in topology or loss of link, the node is not compensated, which means either packet transmission would be halted or repaired or restarted.

It can be classified into following two types:

- Shortest Path Routing
· Flooding

Shortest Path Routing

Shortest path routing algorithm determines the shortest path between nodes on network and select the shortest route. In general sense, the labels on the link can be computed as a function of distance, communication cost, delay, average traffic, bandwidth, queue length etc. The node to transmit has to determine the shortest distance to next node overall maintaining shortest path from source node to sink node.

Flooding

In flooding, every node in network transmits packets to all neighbouring nodes creating huge amounts of duplicate or redundant packets. In case of WSNs, flooding can be used when all the messages transmitted by a station are received by all other stations within their communication range.

Flooding creates overall congestion, network load and also utilizes much energy of each and every node in the network.

Adaptive Routing Algorithms

Most of wireless communication networks makes use of Adaptive routing algorithms. The Adaptive routing algorithms (Dynamic Routing Algorithms) change their respective routing decision with regard to any sort of change in network topology and traffic load.

Adaptive routing mainly defines the ability of the system, in calculating the optimized routes from source to destination and to modify the path the route takes through the system with regard to changing conditions. Adaptive routing is basically designed to allow as many as routes as possible to cope up with packet loss, in response to any sort of change in the network. Adaptive routing is utilized in networking to describe the ability of network to make changes in route discovery, path establishment and data transfer between nodes.

Adaptive routing is broadly classified into following three main categories: Data Centric, Hierarchical and Location based routing protocols. [5, 6, 14]

- Data Centric Routing (Flat Routing): Depending on the applications, where tons of sensor nodes are deployed, it becomes really challenging to assign Global Identifiers to each node [15, 16]. With the utter lack of global identifications in addition to random deployment of nodes, it becomes really difficult to query a specific sensor node. This leads to redundancy in entire network. This problem has led to development of Data-Centric routing. In data-centric routing, the sink sends queries to certain regions and wait for data to be received back from sensors located in selected regions. Data Centric protocols are: SPIN, Directed Diffusion, Rumor Routing, GBR, MCFA, CADR, COUGAR, ACQUIRE, EAR.

- Hierarchical Routing: Hierarchical Routing or Cluster based routing [14] are regarded as specialized techniques providing specific advantages in terms of scalability and efficient communication to wireless sensor networks. As sensor nodes are not capable of long-haul communication, single gateway architecture is not scalable for large set of sensors. Network clustering has been proposed in various routing protocols to balance additional traffic load and cover large area without depreciating the service quality. In hierarchical based architecture, the nodes with higher energy are used to process and transmit the information while low energy nodes perform the task of sensing in the proximity of the target which leads to cluster creation and cluster head performs specific tasks making the overall WSN network scalable and energy efficient. The main objective of hierarchical routing is to maintain energy efficiency of nodes by using multi-hop communication in cluster and perform data aggregation to reduce transmitted packets. It is basically two-layer routing in which one layer makes the selection of cluster heads and other layer performs routing process. Hierarchical protocols are: LEACH, TEEN & APTEEN, MECN& SMECN, SOP, HPAR, VGA, SENSOR Aggregate and TIDD.

- Location based protocols: Location based protocols [14] are required to calculate the distance between two sensor nodes to determine the energy consumption. Location based protocols use the position information to spread the data to desired regions rather than entire network. As, there is no utilization of addressing scheme as in IP-addressed networks, location information can be used to route data from source node to destination node in energy efficient way. Location based protocols are GAF, GEAR, SPAN, MFR & GEDIR and GOAFR.

Swarm Intelligence and Ant Colony Optimization

1.8 Swarm and Swarm Intelligence (SI)

In the past few decades, the coordinated and complex behaviour of swarms have also been a source of interest for biologists and also computer scientists because of amazing efficiency in solving complex problems. In 1989, the concept of “Swarm Intelligence” was proposed by G. Beni and J. Wang [32]. Particle Swarm Optimization (PSO) based on Birds and Fish Swam (FS) based on fishes are regarded as the most important examples of coordinated behaviour that emerges without any need of centralized control [29]. Social insect colonies like Ants, Termites demonstrate complex problem solving skills arising from actions and interactions of nonsophisticated individuals.

Natural systems solve multifaceted problems via simple rules, and exhibit organized, complex and intelligent behaviour [30, 31]. Natural process control systems are highly adaptive, evolutionary, distributed (decentralized), reactive and aware of environment.

Considering the foundations of millions of years of evolution, biological based systems and processes have following main characteristics:

- Highly adaptive to dynamically changing environmental conditions.
- Robust and compatible to failures mainly caused by internal or external factors.
- Ability to attain complex behaviors on the basis of limited set of basic rules.
- Ability to learn and evolve when new conditions are applied.
- Self-organization ability in fully-distributed fashion, to achieve efficient equilibrium.
- Best management of constrained resources.
- Surviving capability in harsh environments.

Swarm Intelligence, is the collaborative intelligence of groups of simple individuals, called agents. In simple terms, Swarm Intelligence [26, 27, 28, 41] is regarded as collective behaviour emerged from social insects operating under few defined rules and regulations. With Swarm Intelligence, the developed algorithms have to be highly flexible to adapt internal and external changes and should be highly robust and scalable where individuals fail to be decentralized and self-organized.

Swarm Intelligence lays foundation on following two principles:

I) Self-Organization

II) Stigmergy

Self-Organization

Bonabeau et. al, in Swarm Intelligence, 1999 defined the concept of Self-Organization as,

Self-Organization is a set of dynamical mechanisms whereby structures appear at the global level of a system from interactions of its lower-level components”

Self-organization based system is characterized by following three main parameters:

- Structure: emerges from a homogeneous start-up state. Example: Ants foraging trail, Nest Architecture.

- Multi-stability: coexistence of many stable states. Example: Ants exploits only one of two identical food sources.

- State Transitions: dramatic change of system behavior. Example: Termites operate by moving from non-coordinated to coordinated stage only if their destiny is higher than a threshold value.

Self-Organization has foundation from following four major components:

a) Positive Feedback: It is a simple behavioural “rules of thumb” which lead to structures creation. Examples of positive feedback are: Recruitment and Reinforcement. In terms of ACO, recruitment and reinforcement is “Trail Laying” whereas in PSO is “Birds Flocking”.
b) Negative Feedback: It counterbalances positive feedback and provides backbone for stabilizing collective pattern. Talking of ACO foraging, negative feedback is required at the stage of food source finish, crowding or completion of food source.
c) Fluctuations: It includes random walks, errors, random task-switching. Randomness is most important aspect for emergent structures in terms of new food discovery, locating unexplored food locations and recruitment of nest mates to discovered sources of food.
d) Multiple Interactions: It occurs in swarms as all the agents scatter information with each other coming from other swarms so that data spread across entire network and swarms can have self-organization movement from nests to food sources.

Self-Organization is very well achieved by swarms via two sorts of communication: Direct Communication and Indirect Communication.

Stigmergy

The term “Stigmergy” [38, 39] was introduced by Grassé. The word “Stigmergy” comprises of two words: Stigma meaning Sting and Ergon meaning work and in turn means Stimulation by work. In addition to Self-organization, stigmergy is also an important term which defines work coordination and also work doesn’t depend solely on workers.

In insects, stigmergy is closely observed. In terms of ants, ants exchange the path from nest to food source by splitting pheromone on the way so that other ants follow the trail and lay the foundation of food transport from food source to nest.

Taking stigmergy with respect to computer science, stigmergy can be applied via Ant Colony Optimization, in which ACO technique searches for solutions to various complex problems via “Virtual Pheromones” and choosing the best path as solution.

Stigmergy is of following types:

1) Sign-based Stigmergy: Pheromone based trail following by ants from nest to food source.
2) Sematactonics: nest building by termites.
3) Quantitative: Trail-laying and following behavior of ants.
4) Quantitative: Nest building by social wasps.

Swarm Intelligence based algorithms and techniques are used in varied optimizations tasks and research areas. Swarm Intelligence principles are successfully applied in various problem solving domains including function optimization problems, determining efficient routes, image and data processing [33, 34].

To understand, model and simulate the broad behaviors arising from Swarm Agents, the following are some of the principles of Swam Intelligence defined by Millonas in 1999: [24, 25, 40]

- Principle of Proximity: The swarm are regarded as highly capable agents of performing simple computations relating to the surrounding environment. The computation is regarded as direct response to behavior with regard to environmental variations. Depending on the agent complexity, responses vary from situation to situation like searching for food in live changing environment considering all sorts of natural and path obstacles and nest construction by ants.

- Principle of Quality: In addition to solving complex computation problems, a swarm should response to various quality factors like food, safety in harsh environment and adapting to changes in environment.
- Principle of diverse response: With regard to resources, concentration should be in narrow areas. The search of food by agents should be such organized that every agent should be protected against all sorts of changing conditions in environment.
- Principle of Stability and Adaptability: All sorts of environmental problems should be efficiently tackled by swarms and should save all resources in terms of costs and energy in search of food resource.

The most popular Swarm Intelligence based algorithms [25, 29, 30, 35, 36] are Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Artificial Bee Colony (ABC), Bacterial Foraging, Fish Swarm, Cuckoo Search, Bat Algorithm, Pigeon Swarm, Elephant Swarm, Cockroach Swarm, Firefly Algorithm, Cat Swarm, Glow-worm Swarm Algorithm, Flower Pollination Algorithm and many more.

Human beings when possibly stuck in hard complex computation problems, always move towards Swarm Intelligence based algorithms. On Swarm Intelligence grounds, social insects (agents) play a dramatic role in problem solving because of their natural intelligence. Social Insects solve the problem individually or via self-cooperation. Ants based swarm search for food highly demonstrates the ability to determine the shortest path from source to nest. A flock of birds fly across of sky without a single collision lay a strong foundation for telecommunications and networks based problems of collision avoidance. A school of fish swim together. This kind of collective behavior known as swam intelligence can be applied to tons of engineering issues and problems to determine the solutions to model the behavior via mathematical analysis and simulation. With the use of ants and other social swarms as models, the development of software agents is possible to find solution to complex problem like rerouting the traffic in busy telecommunication network [37].

In this thesis, we focus primarily on the most popular Swarm Intelligence technique utilized by various researchers to solve various issues of Wireless Sensor Networks, namely, Ant Colony Optimization.

1.9 Ant Colony Optimization (ACO)

1.9.1 Introduction

The concept of “ANT COLONY OPTIMIZATION” [42, 43, 44, 45, 46, 47, 48] was coined by Marco Dorigo and colleagues for finding solutions to hard combinatorial optimization (CO) problems. It is probabilistic technique and ACO algorithm is member of ant colony algorithms family in the broad area of Swarm Intelligence which consists of some meta-heuristic optimizations. The concept of Ant Colony Optimization was basically developed and conceptualized by Marco Dorigo [44] in his Ph.D Thesis as first algorithm whose basic aim was to find the shortest path in the graph by conceptualizing the problem based on ants finding food from their respective colonies to the food source.

The proceeding section outlines ants in nature, Ants Stigmergic behavior, Real Ants v/s Artificial Ants, ACO Metaheuristic and ACO based Algorithms- Ant System (AS), Ant Colony System (ACS) and MAX-MIN Ant System (MMAS).

1.9.2 Ants in Nature

Ants are able to survive tons of dynamic changing environments, climates. The secret behind the success of survivability of ants against all sorts of harsh environments is Sociality [50]. Ants colonies [48, 49], more specifically social insects are distributed systems that, in spite of simplicity of individuals, present a highly structured social organization. As a result, they live in organized societal setup made of agents that cooperate, communicate and divide the tasks equally for solving complex problems. The main backbone behind Ants coordination is Self-Organization principle which demonstrates impressive abilities in doing varied tasks like shortest path searching, nest building and locating food source and laying the trail of pheromone for food transport from source to nest. Biologists have demonstrated that Stigmergic, indirect-communication which demonstrates how a social agent achieve self-organization. Ants being highly efficient, hardworking and highly adaptable to changing conditions leads to applicability of Ants based algorithms in different engineering disciplines.

1.9.3 Ants Stigmergic behavior

Stigmergy, being a biological term is related with insect depicting swarm behavior and describes a model supporting environmental communication separately from artefacts or agents. Ants, being social insects like many other swarm agents, communicate via chemical substance known as pheromones which lays the foundation of direction and intensity of food. The word “pheromone” was coined by P.Karlson and M.Lusher in 1959, where pherein means transport and hormone means stimulate [51]. Insects use different types of pheromones. Talking of ants, two main types of pheromone which are used by them are: Alert Pheromone- which alerts the ants to alert regarding nearby dangerous predators to protect their respective ant colonies; Food Trail Pheromone- where other ants follow the trail of pheromone from start (Nest) to Destination (Food Source). Ants which make the shortest path from source to food and back to nest will attract other ants to follow as seen in figure 3.1. Positive feedback process is example of self-organization behavior of ants to determine the probability of selecting the shortest path and the level of pheromone increases as more ants traverse the same path.

Abbildung in dieser Leseprobe nicht enthalten

Fig. 1.11. Ants stigmergic behavior

After transferring the whole food from source to nest, no pheromone trail is laid by ants returning back and pheromone being chemical substance gets evaporated with passage of time. This sort of negative feedback enables ants to handle the environmental changes. When the path is obstructed by any sort of obstacles, the ants search for new paths. Such sort of trail-laying and following behavior is known as Stigmergy and usually regarded as indirect communication in which ants automatically change with environment and responds to new environment automatically. [30, 34]

1.9.4 Real Ants v/s. Artificial Ants

Real Ants are those which use natural phenomenon to discover optimal paths, search food in the environment via probability, build nests and lay pheromone trail. Artificial Ants is regarded as developing a nature inspired algorithm based on real ants. Natural phenomenon is highly constrained and can be only done via observations and experiments. Development of nature inspired algorithm is totally dependent on one’s understanding towards working of algorithm, mathematical computations deriving the behavior and technology to simulate the model. Ant Colony Optimization (ACO), is completely based on real ants social behavior, but it is not possible to design artificial ants as the same replica. Modeling is regarded as interface between natural behavior understanding and development of artificial systems. Technically, researchers start with natural phenomenon observation, develop a nature-inspired model of then and then artificial system of it without any sort of constraints.

Table 1.2. Real Ants V/s Artificial Ants.

Abbildung in dieser Leseprobe nicht enthalten

Table 1.2 defines the possible differences between real ants and artificial ants. “Memory” is one of the major difference between real and artificial ants. This memory lays the foundation for artificial ant to implement a large number of effective behaviors to build solutions to complex problems.

[...]