Title: On bounding node-to-sink latency in wireless sensor networks with multiple sinks

Authors: Donghyun Kim; Wei Wang; Weili Wu; Deying Li; Changcun Ma; Nassim Sohaee; Wonjun Lee; Yuexuan Wang; Ding-Zhu Du

Addresses: Department of Mathematics and Computer Science, North Carolina Central University, Durham, NC 27707, USA ' Department of Mathematics, Xi'an Jiaotong University, Xi'an, 710049, China ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA ' School of Information, Renmin University of China, Beijing, 100872, China ' Institute for Theoretical Computer Science, Tsinghua University, Beijing 100084, China ' Division of Liberal Arts & Life Sciences, University of North Texas at Dallas, Dallas, TX 75241, USA ' Department of Computer Science and Engineering, Korea University, Seoul, 136-713, South Korea ' Institute for Theoretical Computer Science, Tsinghua University, Beijing, 100084, China ' Department of Computer Science, University of Texas at Dallas, Richardson, TX 75083, USA; WCU FNOT Research Center, Korea University, Seoul, 136-713, South Korea

Abstract: Bounding node-to-sink latency is an important issue of wireless sensor networks (WSNs) with a quality of service requirement. This paper proposes to deploy multiple sinks to control the worst case node-to-sink data latency in WSNs. The end-to-end latency in multihop wireless networks is known to be proportional to the hop length of the routing path that the message moves over. Therefore, we formulate the question of what is the minimum number of sinks and their locations to bound the latency as the minimum d-hop sink placement problem. We also consider its capacitated version. We show problems are NP-hard in unit disk graph (UDG) and unit ball graph, and propose constant factor approximations of the problems in both graph models. We further extend our algorithms so that they can work well in more realistic quasi UDG model. A simulation study is also conducted to see the average performance of our algorithms.

Keywords: WSNs; wireless sensor networks; multiple sink placement; relay node placement; mobile computing; approximation algorithms; graph theory; unit disk graph; UBG; unit ball graph; quasi UDG; node-to-sink latency; multiple sinks; wireless networks.

DOI: 10.1504/IJSNET.2013.052729

International Journal of Sensor Networks, 2013 Vol.13 No.1, pp.13 - 29

Received: 05 Jul 2012
Accepted: 08 Nov 2012
Published online: 19 Mar 2013 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article