Localizability of Wireless Sensor Networks: Beyond Wheel Extension
Pages 326 - 340
Abstract
A network is called localizable if the positions of all the nodes of the network can be computed uniquely. If a network is localizable and embedded in plane with generic configuration, the positions of the nodes may be computed uniquely in finite time. Therefore, identifying localizable networks is an important function. If the complete information about the network is available at a single place, localizability can be tested in polynomial time. In a distributed environment, networks with trilateration orderings (popular in real applications) and wheel extensions (a specific class of localizable networks) embedded in plane can be identified by existing techniques. We propose a distributed technique which efficiently identifies a larger class of localizable networks. This class covers both trilateration and wheel extensions. In reality, exact distance is almost impossible or costly. The proposed algorithm based only on connectivity information. It requires no distance information.
References
[1]
Aspnes, J., Eren, T., Goldenberg, D., Morse, A., Whiteley, W., Yang, Y., Anderson, B., Belhumeur, P.: A theory of network localization. IEEE Transactions on Mobile Computingä5(12), 1663—1678 (2006)
[2]
Biswas, P., Toh, K.-C., Ye, Y.: A distributed sdp approach for large-scale noisy anchor-free graph realization with applications to molecular conformation. SIAM J. Sci. Comput.ä30(3), 1251—1277 (2008), http://dx.doi.org/10.1137/05062754X
[3]
Cakiroglu, A., Erten, C.: Fully decentralized and collaborative multilateration primitives for uniquely localizing wsns. EURASIP Journal on Wireless Communications and Networking 2010, Article ID 605658, 7 pages (2010)
[4]
Čapkun, S., Hamdi, M., Hubaux, J.P.: Gps-free positioning in mobile ad hoc networks. Cluster Computingä5, 157—167 (2002)
[5]
Connelly, R.: Generic global rigidity. Discrete and Computational Geometryä33(4), 549—563 (2005), http://dx.doi.org/10.1007/s00454-004-1124-4
[6]
Hendrickson, B.: Conditions for unique graph realizations. SIAM J. Comput.ä21, 65—84 (1992)
[7]
Jackson, B., Jordán, T.: Connected rigidity matroids and unique realizations of graphs. Journal of Combinatorial Theory Series Bä94(1), 1—29 (2005)
[8]
Kwon, O.H., Song, H.J., Park, S.: Anchor-free localization though flip-error-resistant map stitching in wireless sensor network. IEEE Transactions on Parallel and Distributed Systemsä21(11) (2010)
[9]
Laman, G.: On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematicsä4(4) (December 1970)
[10]
Moore, D., Leonard, J., Rus, D., Teller, S.: Robust distributed network localization with noisy range measurements. In: SenSys 2004: Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, pp. 50—61. ACM, New York (2004), http://doi.acm.org/10.1145/1031495.1031502
[11]
Niculescu, D., Nath, B.: Dv based positioning in ad hoc networks. Journal Telecommunication Systemsä22, 267—280 (2003)
[12]
Sau, B., Mukhopadhyaya, K.: Length-based anchor-free localization in a fully covered sensor network. In: Proc. of the First International Conference on COMmunication Systems and NETworks, COMSNETS 2009, pp. 137—146. IEEE Press, Piscataway (2009), http://dl.acm.org/citation.cfm?id=1702135.1702157
[13]
Sau, B., Mukhopadhyaya, K.: Localizability of wireless sensor networks: Beyond wheel extension. ArXiv e-prints (August 2013), http://arxiv.org/abs/1308.6464
[14]
Savvides, A., Han, C., Strivastava, M.: Dynamic fine-grained localization in ad-hoc networks of sensors. In: Proc. of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom 2001), pp. 166—179. ACM, Rome (2001)
[15]
Saxe, J.: Embeddability of weighted graphs in k-space is strongly np-hard. In: Proc. 17th. Allerton Conference in Communications, Control and Computing, pp. 480—489 (1979)
[16]
Yang, Z., Liu, Y., Li, X.: Beyond trilateration: on the localizability of wireless ad hoc networks. IEEE/ACM Trans. Netw.ä18(6), 1806—1814 (2010)
[17]
Zhu, Z., So, A.C., Ye, Y.: Universal rigidity: Towards accurate and efficient localization of wireless networks. In: IEEE INFOCOM 2010 (2010)
- Localizability of Wireless Sensor Networks: Beyond Wheel Extension
Recommendations
Understanding Node Localizability of Wireless Ad Hoc and Sensor Networks
Location awareness is highly critical for wireless ad-hoc and sensor networks. Many efforts have been made to solve the problem of whether or not a network can be localized. Nevertheless, based on the data collected from a working sensor network, it is ...
Assuring Location Estimation Accuracy of Anchor-Free Mobile Localization in Wireless Sensor Networks
ICDCSW '13: Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems WorkshopsAnchor-free localization algorithms do not depend on the existence of anchor objects. Since no anchor objects are required, the localization algorithm can still be applied to problems for which setting anchor objects is difficult. In the anchor-free ...
Reference Anchor Selection and Global Optimized Solution for DV-Hop Localization in Wireless Sensor Networks
Localization is a fundamental issue in wireless sensor networks (WSN). Among typical range-free localization algorithms, distance vector-hop (DV-Hop) is preferred as it can localize unknown nodes with less than three neighbor anchors. However, the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2013
378 pages
ISBN:9783319030883
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 13 November 2013
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 13 Dec 2024