News Archives

  • UNM
  • >Home
  • >News
  • >2011
  • >September
  • >[Colloquium] Constrained Relay Node Placement in Wireless Sensor Networks: Formulation and Approximations

[Colloquium] Constrained Relay Node Placement in Wireless Sensor Networks: Formulation and Approximations

September 16, 2011

Watch Colloquium: 

M4V file (612 MB)

  • Date: Friday, September 16, 2011 
  • Time: 12:00 pm — 12:50 pm 
  • Place: Centennial Engineering Center 1041

Satyajayant Misra
New Mexico State University

Deployment characteristics of sensor nodes and their energy limited nature affects network connectivity, lifetime, and fault-tolerance of wireless sensor networks (WSNs). One approach to address these issues is to deploy some relay nodes to communicate with the sensor nodes, other relay nodes, and the base stations in the network. The relay node placement problem for WSNs is concerned with placing a minimum number of relay nodes into a WSN to meet certain connectivity or survivability requirements. Previous studies have concentrated on the unconstrained version of the problem in the sense that relay nodes can be placed anywhere. In practice, there may be some physical constraints on the placement of relay nodes. To address this issue, we have studied constrained versions of the relay node placement problem, where relay nodes can only be placed at a set of candidate locations.

I will talk about relay node placement for connectivity and survivability, we will discuss the computational complexity of the problems and look at a framework of polynomial time O(1)-approximation algorithms with small approximation ratios. I will share our numerical results. We will also talk about some pertinent extensions of this work in the area of high performance computing.

Bio: Dr. Satyajayant Misra is an assistant professor at New Mexico State University (from fall 2009). His research interests include anonymity, security, and survivability in wireless sensor networks, wireless ad hoc networks, and vehicular networks and optimized protocol designs for next supercomputing architectures.

Dr. Misra serves on the editorial boards of the IEEE Communications on Surveys and Tutorials and the IEEE Wireless Communications Magazine. He is the TPC Vice-Chair of Information Systems for the IEEE INFOCOM 2012. He has served on the executive committees of IEEE SECON 2011 and IEEE IPCCC 2010. He is the recipient of New Mexico State University’s University Research Council Early Career Award for Exceptional Achievement in Creative Scholastic Activity, for the year 2011.