Force-directed approaches to sensor localization

Alon Efrat; David Forrester; Anand Iyer; Stephen G. Kobourov; Cesim Erten

doi:10.1137/1.9781611972863.11

Force-directed approaches to sensor localization

Alon Efrat, David Forrester, Anand Iyer, Stephen G. Kobourov, Cesim Erten

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

12 Scopus citations

Abstract

We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.

Original language	English (US)
Title of host publication	Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
Publisher	Society for Industrial and Applied Mathematics Publications
Pages	108-118
Number of pages	11
ISBN (Print)	0898716101, 9780898716108
DOIs	https://doi.org/10.1137/1.9781611972863.11
State	Published - 2006
Event	8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics - Miami, FL, United States Duration: Jan 21 2006 → Jan 21 2006

Publication series

Name	Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
Volume	2006

Other

Other	8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics
Country/Territory	United States
City	Miami, FL
Period	1/21/06 → 1/21/06

ASJC Scopus subject areas

General Engineering

Access to Document

10.1137/1.9781611972863.11

Cite this

Efrat, A., Forrester, D., Iyer, A., Kobourov, S. G., & Erten, C. (2006). Force-directed approaches to sensor localization. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics (pp. 108-118). (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics; Vol. 2006). Society for Industrial and Applied Mathematics Publications. https://doi.org/10.1137/1.9781611972863.11

Force-directed approaches to sensor localization. / Efrat, Alon; Forrester, David; Iyer, Anand et al.
Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics. Society for Industrial and Applied Mathematics Publications, 2006. p. 108-118 (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics; Vol. 2006).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Efrat, A, Forrester, D, Iyer, A, Kobourov, SG & Erten, C 2006, Force-directed approaches to sensor localization. in Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics. Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics, vol. 2006, Society for Industrial and Applied Mathematics Publications, pp. 108-118, 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics, Miami, FL, United States, 1/21/06. https://doi.org/10.1137/1.9781611972863.11

Efrat A, Forrester D, Iyer A, Kobourov SG, Erten C. Force-directed approaches to sensor localization. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics. Society for Industrial and Applied Mathematics Publications. 2006. p. 108-118. (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics). doi: 10.1137/1.9781611972863.11

Efrat, Alon ; Forrester, David ; Iyer, Anand et al. / Force-directed approaches to sensor localization. Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics. Society for Industrial and Applied Mathematics Publications, 2006. pp. 108-118 (Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics).

@inproceedings{a089d9b92d8f4925aa0b75cbf5fcbf02,

title = "Force-directed approaches to sensor localization",

abstract = "We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.",

author = "Alon Efrat and David Forrester and Anand Iyer and Kobourov, {Stephen G.} and Cesim Erten",

year = "2006",

doi = "10.1137/1.9781611972863.11",

language = "English (US)",

isbn = "0898716101",

series = "Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics",

publisher = "Society for Industrial and Applied Mathematics Publications",

pages = "108--118",

booktitle = "Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics",

address = "United States",

note = "8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics ; Conference date: 21-01-2006 Through 21-01-2006",

}

TY - GEN

T1 - Force-directed approaches to sensor localization

AU - Efrat, Alon

AU - Forrester, David

AU - Iyer, Anand

AU - Kobourov, Stephen G.

AU - Erten, Cesim

PY - 2006

Y1 - 2006

N2 - We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.

AB - We consider the centralized, anchor-free sensor localization problem. We consider the case where the sensor network reports range information and the case where in addition to the range, we also have angular information about the relative order of each sensor's neighbors. We experimented with classic and new force-directed techniques. The classic techniques work well for small networks with nodes distributed in simple regions. However, these techniques do not scale well with network size and yield poor results with noisy data. We describe a new force-directed technique, based on a multi-scale dead-reckoning, that scales well for large networks, is resilient under range errors, and can reconstruct complex underlying regions.

UR - http://www.scopus.com/inward/record.url?scp=33646837697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646837697&partnerID=8YFLogxK

U2 - 10.1137/1.9781611972863.11

DO - 10.1137/1.9781611972863.11

M3 - Conference contribution

AN - SCOPUS:33646837697

SN - 0898716101

SN - 9780898716108

T3 - Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

SP - 108

EP - 118

BT - Proceedings of the 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

PB - Society for Industrial and Applied Mathematics Publications

T2 - 8th Workshop on Algorithm Engineering and Experiments and the 3rd Workshop on Analytic Algorithms and Combinatorics

Y2 - 21 January 2006 through 21 January 2006

ER -

Force-directed approaches to sensor localization

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this