skip to main content
10.1145/1374618.1374667acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
research-article

Challenging benchmark for location discovery in ad hoc networks: foundations and applications

Published: 26 May 2008 Publication History

Abstract

We have created the first comprehensive and challenging benchmark data set for the ad-hoc location discovery (LD). The benchmark is a collection of representative real-life distance measurement data that establishes a common basis for understanding, characterization, evaluation and comparison of the LD algorithms and solvers. It is constructed using a novel analysis methodology that systematically establishes the difficulty of discovering the locations. Presence of measurement noise renders the problem difficult even in dense networks. The noise impacts the continuous optimization underlying the LD calculations. We focus on the difficulty of node localization in dense networks. In such networks, the location calculation is viewed as a continuous optimization problem instance with an objective function and a set of constraints. We devise a number of new metrics that evaluate the difficulty of the continuous optimization based on the data set properties. For the LD optimization, a fast simulation methodology is devised for rapid analysis of the sensitivity of the goodness with respect to the data set properties. We present a number of applications for the benchmark data and use it for evaluation and comparison of six popular LD algorithms. The LD benchmarks are publicly available at: http://www.ece.rice.edu/~mm7/benchLD/.

References

[1]
S. Megerian, F. Koushanfar, M. Potkonjak, and M. Srivastava, "Worst- and best-case coverage in sensor networks," IEEE Transactions on Mobile Computing, vol. 4, no. 1, pp. 84--92, 2005.
[2]
S. Megerian, F. Koushanfar, G. Qu, G. Veltri, and M. Potkonjak, "Exposure in wireless sensor networks: Theory and practical solutions," ACM Journal of Wireless Networks, vol. 8, no. 5, pp. 443--454, 2002.
[3]
S. Meguerdichian, S. Slijepcevic, V. Karayan, and M. Potkonjak, "Localized algorithms in wireless ad-hoc networks: location discovery and sensor exposure," in MobiHoc, 2001, pp. 106--116.
[4]
F. Koushanfar, N. Taft, and M. Potkonjak, "Sleeping coordination for comprehensive sensing using isotonic regression and domatic partitions," in Infocom, 2006, pp. 1--13.
[5]
"http://cricket.csail.mit.edu, seen in nov. 2007."
[6]
"http://wwwosl.cs.uiuc.edu/research?action=topic&topic=sensor+networks, seen in nov. 2007."
[7]
L. Girod, M. Lukac, V. Trifa, and D. Estrin, "The design and implementation of a self-calibrating distributed acoustic sensing platform," in Sensys, 2006, pp. 71--84.
[8]
A. Savvides, C. Han, and M. Strivastava, "Dynamic fine-grained localization in ad-hoc networks of sensors," in Mobicom, 2001, pp. 166--179.
[9]
C. Savarese, J. Rabaey, and K. Langendoen, "Robust positioning algorithms for distributed ad-hoc wireless sensor networks," in USENIX, 2002, pp. 317--327.
[10]
F. Koushanfar, S. Slijepcevic, M. Potkonjak, and A. Sangiovanni-Vincentelli, Location Discovery in Ad-hoc Wireless Sensor Networks. Kluwer, 2003.
[11]
N. Kiyavash and F. Koushanfar, "Anti-collusion position estimation in wireless sensor networks," in IEEE Internatonal conference on Mobile Adhoc and Sensor Systems (MASS), 2007, pp. 1--9.
[12]
K. Langendoen and N. Reijers, "Distributed localization in wireless sensor networks: a quantitative comparison," Computer Networks, vol. 43, no. 4, pp. 499--518, 2003.
[13]
L. Hu and D. Evans, "Localization for mobile sensor networks," in Mobicom, 2004, pp. 45--57.
[14]
J. Feng, L. Girod, and M. Potkonjak, "Location discovery using data-driven statistical error modeling," in Infocom, 2006, pp. 1--14.
[15]
J. Feng and M. Potkonjak, "Consistency error modeling-based localization in sensor networks," in SECON, 2006, pp. 356--364.
[16]
J. Feng, L. Girod, and M. Potkonjak, "Consistency-based on-line localization in sensor networks," in DCOSS, 2006, pp. 529--545.
[17]
M. Carey, D. DeWitt, and J. Naughton, "The oo7 benchmark," in SIGMOD, 1993, pp. 12--21.
[18]
C. Lee, W. Mangione-Smith, and M. Potkonjak, "Mediabench: A tool for evaluating multimedia and communication systems," in MICRO, 1997, pp. 330--335.
[19]
R. Baeza-Yates and B. Ribeiro-Neto, Modern Information Retrieval. Addison-Wesley, 1999.
[20]
R. Plackett and J. Burman, "The design of optimum multifactorial experiments," Biometrika, vol. 33, no. 4, pp. 305--325, 1946.
[21]
{21} G. Box and J. Hunter, "The 2k?p fractional factorial designs parts I and II," Technometrics, vol. 3, no. 3/4, pp. 311--351/449--458, 1961.
[22]
Center for Embedded Networked sensing, "http://research.cens.ucla.edu/."
[23]
J. Saxe, "Embeddability of weighted graphs in k-space is strongly NP-hard," in Allerton, 1979, pp. 480--489.
[24]
H. Breu and D. G. Kirkpatrick, "Unit disk graph recognition is NP-hard," Computational Geometry, vol. 9, no. 1-2, pp. 3--24, 1998.
[25]
D. Achlioptas, A. Naor, and Y. Peres, "Rigorous location of phase transitions in hard optimization problems," Nature, no. 435, pp. 759--764, 2005.
[26]
CPLEX mathematical optimization package, seen in Nov. 2007, "http://www.ilog.com/products/cplex/."
[27]
Localization simulator, seen in Nov. 2007, "http://www.cs.virginia.edu/ whitehouse/research/localization/."
[28]
K. Whitehouse and D. Culler, "A robustness analysis of multi-hop ranging-based localization approximations," in IPSN, 2006, pp. 317--325.
[29]
Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, "Localization from mere connectivity," in MobiHoc, 2003, pp. 201--212.
[30]
Y. Shang and W. Ruml, "Improved mds-based localization," in Infocom, 2004, pp. 2640--2651.
[31]
A. Savvides, H. Park, and M. B. Srivastava, "The bits and flops of the n-hop multilateration primitive for node localization problems," in IWSNA, 2002, pp. 112--121.
[32]
D. Niculescu and B. Nath, "Ad hoc positioning system (aps)," in Globecom, 2001, pp. 2926--2931.

Cited By

View all
  • (2008)Multiple statistical validations for sensor networks optimization2008 International Conference on Innovations in Information Technology10.1109/INNOVATIONS.2008.4781758(544-547)Online publication date: Dec-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing
May 2008
474 pages
ISBN:9781605580739
DOI:10.1145/1374618
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 May 2008

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. NP-complete problem
  2. add hoc networks
  3. benchmarks
  4. hard instances
  5. localization

Qualifiers

  • Research-article

Conference

MobiHoc08
Sponsor:

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2008)Multiple statistical validations for sensor networks optimization2008 International Conference on Innovations in Information Technology10.1109/INNOVATIONS.2008.4781758(544-547)Online publication date: Dec-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media