Analytical characterization of computationally efficient localization techniques

Motevallian, SA; Mao, G; Anderson, BDO

Analytical characterization of computationally efficient localization techniques

Motevallian, SA Mao, G

Anderson, BDO

Permalink

Publication Type:: Conference Proceeding
Citation:: IEEE Wireless Communications and Networking Conference, WCNC, 2013, pp. 2131 - 2136
Issue Date:: 2013-08-21

Closed Access

	Filename	Description	Size
	2013001497OK.pdf		1.03 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Motevallian, SA	en_US
dc.contributor.author	Mao, G https://orcid.org/0000-0002-3598-4949	en_US
dc.contributor.author	Anderson, BDO	en_US
dc.date.issued	2013-08-21	en_US
dc.identifier.citation	IEEE Wireless Communications and Networking Conference, WCNC, 2013, pp. 2131 - 2136	en_US
dc.identifier.isbn	9781467359399	en_US
dc.identifier.issn	1525-3511	en_US
dc.identifier.uri	http://hdl.handle.net/10453/29971
dc.description.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 trilateration-based 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 bilateration-based 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 bilateration-based 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. © 2013 IEEE.	en_US
dc.relation.ispartof	IEEE Wireless Communications and Networking Conference, WCNC	en_US
dc.relation.isbasedon	10.1109/WCNC.2013.6554892	en_US
dc.title	Analytical characterization of computationally efficient localization techniques	en_US
dc.type	Conference Proceeding
utslib.for	0805 Distributed Computing	en_US
utslib.for	080501 Distributed and Grid Systems	en_US
utslib.for	100503 Computer Communications Networks	en_US
dc.location.activity	Shanghai	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Electrical and Data Engineering
pubs.organisational-group	/University of Technology Sydney/Strength - CRIN - Realtime Information Networks
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

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 trilateration-based 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 bilateration-based 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 bilateration-based 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. © 2013 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/29971