Optimal placement of relay nodes in wireless sensor network using artificial bee colony algorithm
Journal of Network and Computer ApplicationsPublished 17 February 2016Open access
Hashim A. Hashim, Babajide O. Ayinde, M. A. Abido
Citations121
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The ABC-based deployment is guaranteed to extend the lifetime by optimizing the network parameters and constraining the total number of deployed relays and demonstrates the efficacy of the proposed deployment strategy under different cases of problem complexity.
Abstract
Deploying sensor nodes randomly most of the time generates initial\ncommunication hole even in highly dense networks. These communication holes\ncannot be totally eliminated even when the deployment is done in a structured\nmanner. In either case, the resulting inter-node distances may degrade the\nperformance of the network. This paper proposes an enhanced deployment\nalgorithm based on Artificial Bees Colony (ABC). The ABC-based deployment is\nguaranteed to extend the lifetime by optimizing the network parameters and\nconstraining the total number of deployed relays. Simulations validate the\neffectiveness of the proposed strategy under different cases of problem\ncomplexity. Results show that the proposed approach improves the network\nlifetime considerably when compared to solutions reported in the literature\nsuch as Shortest Path 3-D grid Deployment (SP3D) algorithm.\n Keywords: Artificial Bee Colony, Wiener index, optimization, relay nodes,\nLaplacian matrix, connected graph, vertex, edge, average distance, Laplacian\nmatrix, Shortest Path 3-D grid Deployment, ABC, SP3D, RNs/CHs, ILDCC, SPRN,\nO3DwLC, algorithm, approach, single objective, multi objective, eigenvalue,\nFirst Phase Relay Nodes, NP-Hard, Deployment, proposed, second phase relay\nnodes, Ideal Media Access Control, cluster head, Minimum Spanning Tree,\nnon-deterministic polynomial-time hard, two-layer hierarchical structure,\nOptimized 3-D deployment with Lifetime Constraints, flux, Wireless Sensor\nNetwork, size, Lifetime, Network load, number of nodes using packets,\nConnectivity, two layered, protocols, collision and interference.\n
Keywords
Computer Science
Journal of Global OptimizationA powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm
7,504 Citations2007Derviş Karaboğa, Bahriye Akay
Artificial Bee Colony (ABC) Algorithm is an optimization algorithm based on the intelligent behaviour of honey bee swarm that is used for optimizing multivariable functions and the results showed that ABC outperforms the other algorithms.
AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION
5,440 Citations2005Derviş Karaboğa
Ad Hoc NetworksStrategies and techniques for node placement in wireless sensor networks: A survey
1,011 Citations2007Mohamed Younis, Kemal Akkaya
This paper reports on the current state of the research on optimized node placement in WSNs, and categorizes the placement strategies into static and dynamic depending on whether the optimization is performed at the time of deployment or while the network is operational, respectively.
Upper bounds on the lifetime of sensor networks
664 Citations2002Manish Bhardwaj, Timothy Garnett +1 more
It is shown that in all data gathering scenarios presented, there exist networks which achieve lifetimes equal to or >95% of the derived bounds, depending on the scenario, and bounds are either tight or near-tight.
Wireless NetworksRelay sensor placement in wireless sensor networks
490 Citations2007Xiuzhen Cheng, Ding‐Zhu Du +2 more
This paper addresses the following relay sensor placement problem: given the set of duty sensors in the plane and the upper bound of the transmission range, compute the minimum number of relay sensors such that the induced topology by all sensors is globally connected.
IEEE Transactions on Mobile ComputingASCENT: adaptive self-configuring sensor networks topologies
477 Citations2004Alberto Cerpa, Deborah Estrin
Growing Well-connected Graphs
342 Citations2006Arpita Ghosh, Stephen Boyd
A new greedy heuristic for the problem of adding edges to a graph so as to maximize its algebraic connectivity is described, based on the Fiedler vector, and therefore can be applied to very large graphs.
IEEE Sensors JournalSensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks
283 Citations2013S. Mini, Siba K. Udgata +1 more
This paper uses artificial bee colony algorithm and particle swarm optimization for sensor deployment problem followed by a heuristic for scheduling that was able to achieve the theoretical upper bound in all the experimented cases.
IEEE Transactions on Parallel and Distributed SystemsMovement-Assisted Connectivity Restoration in Wireless Sensor and Actor Networks
247 Citations2008Ayesha Zaheer Abbasi, Mohamed Younis +1 more
DARA is presented, a distributed actor recovery algorithm, which opts to efficiently restore the connectivity of the interactor network that has been affected by the failure of an actor, and two variants of the algorithm are developed to address 1- and 2-connectivity requirements.
A Design and Implementation of Forest-Fires Surveillance System based on Wireless Sensor Networks for South Korea Mountains
235 Citations2006Byungrak Son, Yong-sork Her +1 more
The developed FFSS (Forest-Fires Surveillance System) consists of WSNs, middleware and web application, which lets to know early alarm in real time when the forest-fire occurs.
Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006Convex optimization of graph Laplacian eigenvalues
195 Citations2007Stephen Boyd
This work considers the problem of choosing the edge weights of an undirected graph so as to maximize or minimize some function of the eigenvalues of the associated Laplacian matrix, subject to some constraints on the weights, such as nonnegativity, or a given total value.
IEEE Transactions on Mobile ComputingRelay Node Deployment Strategies in Heterogeneous Wireless Sensor Networks
171 Citations2009Kenan Xu, Hossam S. Hassanein +2 more
Pervasive and Mobile ComputingImproved sensor network lifetime with multiple mobile sinks
160 Citations2009Mirela Marta, Mihaela Cardei
A distributed and localized algorithm used by mobile sinks to decide their next movement location such that the virtual backbone formed by the sinks remains interconnected at all times is designed.
Journal of Network and Computer ApplicationsAnt colony optimization with greedy migration mechanism for node deployment in wireless sensor networks
131 Citations2013Xuxun Liu, Desi He
This paper considers the problem of grid-based coverage with low-cost and connectivity-guarantee (GCLC) with a novel deployment approach, ACO-Greedy, based on the ant colony optimization with greedy migration mechanism, which can quickly complete the full coverage, and markedly decrease the deployment cost.
Computer CommunicationsEfficient deployment of wireless sensor networks targeting environment monitoring applications
107 Citations2012Fadi Al‐Turjman, Hossam S. Hassanein +1 more
This paper introduces a novel 3-D deployment strategy, called Optimized 3D deployment with Lifetime Constraint (O3DwLC), for relay nodes in environmental applications, which optimizes network connectivity, while guarantying specific network lifetime and limited cost.
IEEE Transactions on Parallel and Distributed SystemsDesign and Deployment of Sensor Network for Real-Time High-Fidelity Volcano Monitoring
93 Citations2010Wen‐Zhan Song, Renjie Huang +3 more
The design and deployment experience of an air-dropped wireless sensor network optimized for rapid deployment during periods of volcanic unrest and provide real-time long-term volcano monitoring is presented.
IEEE Journal on Selected Areas in CommunicationsOptimized relay placement to federate segments in wireless sensor networks
82 Citations2010Sookyoung Lee, Mohamed Younis
A distributed Cell-based Optimized Relay node Placement (CORP) algorithm is proposed and the beneficial aspects of the resulting topology with respect to connectivity, and traffic balance are explained.
Ad Hoc NetworksRelay placement for restoring connectivity in partitioned wireless sensor networks under limited information
70 Citations2013Izzet F. Senturk, Kemal Akkaya +1 more
This paper proposes two distributed relay node positioning approaches to guarantee network recovery for partitioned WSNs by minimizing the movement cost of the relay nodes by exploiting Game Theory among the leaders of the partitions.
Lecture notes in computer scienceImproved Approximation Algorithms for Relay Placement
59 Citations2008Alon Efrat, Sándor P. Fekete +4 more
IEEE Transactions on Industrial ElectronicsGroup Connectivity Model for Industrial Wireless Sensor Networks
55 Citations2009JongHyup Lee, Taekyoung Kwon +1 more
This paper proposes a novel group connectivity model so as to analyze group connectivity and to make a concrete deployment plan of sensor groups with regard to the internal distribution of sensors and group positions and believes that the proposed model should be useful in planning the deployment of wireless sensor networks in harsh industrial environments where running wires is less practical and also prohibitively expensive.
Connectivity Optimization for Wireless Sensor Networks Applied to Forest Monitoring
55 Citations2009Fadi Al‐Turjman, Hossam S. Hassanein +1 more
A generalized RN deployment optimization problem aimed at maximizing the network connectivity with constraints on RNs count is formulated and a threshold on the minimum number of required RNs is set.
Proceedings - IEEE Symposium on Computers and Communications/IEEE Symposium on Computers and CommunicationsOptimal Placement of Relay Nodes in Two-Tiered, Fault Tolerant Sensor Networks
41 Citations2007Ataul Bari, Arunita Jaekel +1 more
This paper has presented a generalized integer linear program (ILP) formulation capable of generating exact solutions for arbitrary values of ks and kr that is applicable to hierarchical sensor networks using relay nodes.
Channel Propagation Model for Mobile Network Project in Densely Arboreous Environments
29 Citations2007Josiane Rodrigues, Simone G. C. Fraiha +4 more
Arabian Journal for Science and EngineeringSensor Node Placement in Wireless Sensor Network Using Multi-objective Territorial Predator Scent Marking Algorithm
27 Citations2014Husna Zainol Abidin, N. M. Din +4 more
Simulation results show that WSN deployed using the MOTPSMA sensor node placement algorithm outperforms the performance of the other two algorithms in terms of coverage, connectivity and energy usage.
Lecture notes in computer scienceArtificial Bee Colony Based Sensor Deployment Algorithm for Target Coverage Problem in 3-D Terrain
20 Citations2011S. Mini, Siba K. Udgata +1 more
This paper finds out the optimal deployment positions in a 3-D terrain using Artificial Bee Colony (ABC) algorithm, which is based on swarm intelligence, and also compares the sensing range requirement for simple, k and Q-coverage problems.
IOSR Journal of Electronics and Communication EngineeringA Modified ABC Algorithm & Its Application to Wireless Sensor Network Dynamic Deployment
14 Citations2013Alina Rakhi Ajayan
An improved ABC algorithm has been proposed to match the different characteristics of wireless sensor network deployment process, which will be optimum for real time dynamic network functioning.
Lecture notes in computer scienceAn Efficient Relay Sensors Placing Algorithm for Connectivity in Wireless Sensor Networks
8 Citations2006Jyh-Huei Chang, Rong‐Hong Jan
Simulation results show that the average number of relay sensors added by minimal spanning tree algorithm is approximately up to two times than ERSPA algorithm.
Simulated annealing approach to optimizing the lifetime of sparse time-driven sensor networks
8 Citations2009María Luisa Santamaría, Sebastià Galmés +1 more
This paper focuses on optimizing the lifetime that can be predicted from the network topology, which is assumed to be a static data gathering tree, and proposes an algorithm based on simulated annealing, which converges asymptotically to the global optimum.
Journal of information science and engineeringAn Efficient Relay Sensor Placing Algorithm for Connectivity in Wireless Sensor Networks
3 Citations2011Jyh-Huei Chang
This paper presents an Efficient Relay Sensor Placing Algorithm (ERSPA) for solving the problem of adding relay sensors such that the underlying graph is connected and the number of relay sensors added is minimized.