Nature-inspired relay node placement heuristics for wireless sensor networks


Ozkan O., Ermiş M.

Journal of Intelligent and Fuzzy Systems, vol.28, no.6, pp.2801-2809, 2015 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 28 Issue: 6
  • Publication Date: 2015
  • Doi Number: 10.3233/ifs-151560
  • Journal Name: Journal of Intelligent and Fuzzy Systems
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.2801-2809
  • Keywords: meta-heuristics, Relay node placement, wireless sensor networks
  • Istanbul Kültür University Affiliated: Yes

Abstract

Wireless Sensor Network (WSN) comprises a large number of spatially distributed sensor devices that can retrieve valuable information via low-cost, low-powered, tiny sensors, and send the data to a sink through its wireless communication units. In order to prolong network lifetime at minimum cost, a small number of powerful relay nodes can be deployed in the sensing area. The connectivity between the sensor nodes and the base stations is one of the most crucial design considerations for WSNs. In this paper, mixed-integer linear programming model of the constrained relay node placement problem is defined. Since the problem has NP-hard nature, novel nature-inspired meta-heuristic methods (Genetic Algorithm (GA) and Simulated Annealing (SA)) are presented to find the number and position of the relay nodes in a heterogeneous WSN. The algorithms have newproblem specific representation and operators. The results of proposedGAis compared with exact, SA and minimum spanning tree solutions. Experimental analysis has shown that presented GA and SA approaches can find a near-optimal or efficient solution in a reasonable computation time.