NDLI: Analytical characterization of computationally efficient localization techniques

Content Provider	IEEE Xplore Digital Library
Author	Motevallian, S.A. Guoqiang Mao Anderson, B.D.O.
Copyright Year	2013
Description	Author affiliation: Australian Nat. Univ., Canberra, ACT, Australia (Motevallian, S.A.; Anderson, B.D.O.) \|\| Sch. of Electr. & Inf. Eng., Univ. of Sydney, Sydney, NSW, Australia (Guoqiang Mao)
Abstract	Trilateration-based localization techniques have been widely used in sensor networks due to their computational efficiency and distributedness. However in sparse networks or in the boundary area of networks, trilateration-based techniques often fail to localize all localizable nodes. Bilateration-based techniques emerge as a generalization of trilateration techniques to a broader class of networks. Compared with trilaterationbased techniques, the main benefit of bilateration-based schemes is that they can localize a higher percentage of nodes while still maintaining the low computational complexity and distributedness properties. One potential drawback of bilaterationbased schemes is that the number of estimated possible positions (hence the memory required to store these positions) may grow exponentially with the number of nodes in the network. Despite the empirical observations reported in the literature that such exponential growth is a rare event, there is a lack of rigorous analysis quantifying the complexity of bilaterationbased schemes. In this paper, we tackle the challenge by first characterizing a broad subclass of the set of critical sub-networks within which the number of possible estimated positions grows exponentially with the size of these sub-networks. Then using mathematical techniques from percolation theory, we prove that, in random geometric networks, with very high probability the size of these critical sub-networks, which constitute the worst case for bilateration-based localization, is bounded. Therefore the complexity of bilateration-based localization technique does not grow exponentially with the size of the entire network. The significance of this result is to analytically demonstrate that bilateration-based techniques not only localize a higher fraction of nodes than their trilateration counterpart, but also they can be implemented in a very efficient (low computational cost) manner.
Starting Page	2131
Ending Page	2136
File Size	612730
Page Count	6
File Format	PDF
ISBN	9781467359382
ISSN	15253511
e-ISBN	9781467359399
e-ISBN	9781467359375
DOI	10.1109/WCNC.2013.6554892
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-04-07
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Topology Upper bound Distance measurement Algorithm design and analysis Computational complexity Educational institutions Trilateration Distributed Localization Bilateration
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient interactive algorithms for file synchronization under general edits

An efficient least-squares trilateration algorithm for mobile robot localization

Analytical Characterization of Computationally Efficient Localization Techniques

A distributed collapse of a network's dimensionality

Topology Matters in Communication

Localized Bridging Centrality for Distributed Network Analysis

Evaluate distance measurement how to influence localization in wireless sensor networks

Message complexity of distributed algorithms revisited

The classification of continuous domains

Analytical characterization of computationally efficient localization techniques

Similar Documents

Efficient interactive algorithms for file synchronization under general edits

An efficient least-squares trilateration algorithm for mobile robot localization

Analytical Characterization of Computationally Efficient Localization Techniques

A distributed collapse of a network's dimensionality

Topology Matters in Communication

Localized Bridging Centrality for Distributed Network Analysis

Evaluate distance measurement how to influence localization in wireless sensor networks

Message complexity of distributed algorithms revisited

The classification of continuous domains

Analytical characterization of computationally efficient localization techniques