Force-Directed Approaches to Sensor Localization

Force-Directed Approaches to Sensor Localization ALON EFRAT, DAVID FORRESTER, ANAND IYER, and STEPHEN G. KOBOUROV University of Arizona CESIM ERTEN Kadir Has University OZAN KILIC Isik University As the number of application areas where sensor networks are used increases, the sensor network localization problem gains more importance. It is the problem of recovering the correct position of each node in a network of sensors from partial connectivity information such as adjacency, range, or angle between neighboring nodes. In this paper,

we consider the anchor-free sensor localization problem in sensor networks that report possibly noisy range information and angular information about the relative order of each sensor’s neighbors. Previously proposed techniques seem to successfully reconstruct the original positions of the nodes for relatively small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with non-convex or non-simple underlying topology. Moreover the distributed nature of the problem makes some of the available techniques useless in a wide range of applications. To address these problems we describe a multi-scale dead-reckoning (MSDR) algorithm that scales well for large networks, can reconstruct complex underlying topologies, and is resilient to noise. The MSDR algorithm takes its roots from classic force-directed graph layout computation techniques. These techniques are appropriately modified with a multi-scale extension to handle the scalability issue and a dead-reckoning extension to overcome the problematic cases arising with non-simple topologies. Furthermore we show that the distributed version of the MSDR algorithm performs as well, if not better than its centralized counterpart, when the qualities of the output layouts measured in terms of appropriate distance metrics are of concern. Categories and Subject Descriptors: C.2.4 [Computer-Communication Networks]: Distributed Systems—Distributed applications; C.2.1 [Computer-Communication Networks]: Network Architecture and Design—Distributed networks General Terms: Algorithms, Experimentation Additional Key Words and Phrases: Sensor networks, node localization, force-directed This work is supported in part by TUBITAK grant 106E071 and NSF grant ACR-0222920. Authors’ addresses: A. Efrat, D. Forrester, A. Iyer, and S. G. Kobourov, Department of Computer Science, University of Arizona, 1040 E 4th Street Tucson, AZ 85721-0077, USA. C. Erten, Kadir Has Universitesi, Kadir Has Caddesi, Cibali, Istanbul 34083, Turkey. O. Kilic, Isik Universitesi, Sile Kampusu, Sile, Istanbul 34980, Turkey. Authors’ email addresses: nullefrat,forrester,iyer,kobourovnull@cs.arizona.edu, cesim@khas.edu.tr, yokilic@isikun.edu.tr. Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. cnull 2010 ACM 0000-0000/2010/0000-0001 $5.00 ACM Journal Name, Vol. X, No. X, X 2010, Pages 1–0??. 2 null Alon Efrat et al. 1. INTRODUCTION...

Website: www.cs.arizona.edu | Filesize: -
No of Page(s): 24
Download Force-Directed Approaches to Sensor Localization - University of ....pdf