Abstract
Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes in a region of Euclidean space. Following deployment, the nodes self-organize into a mesh topology with a key aspect being self-localization. Having obtained a mesh topology in a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this work, we analyze this approximation through two complementary analyses. We assume that the mesh topology is a random geometric graph on the nodes; and that some nodes are designated as anchors with known locations. First, we obtain high probability bounds on the Euclidean distances of all nodes that are h hops away from a fixed anchor node. In the second analysis, we provide a heuristic argument that leads to a direct approximation for the density function of the Euclidean distance between two nodes that are separated by a hop distance h. This approximation is shown, through simulation, to very closely match the true density function.
Localization algorithms that draw upon the preceding analyses are then proposed and shown to perform better than some of the well-known algorithms present in the literature. Belief-propagation-based message-passing is then used to further enhance the performance of the proposed localization algorithms. To our knowledge, this is the first usage of message-passing for hop-count-based self-localization.
- Acharya, S. 2007. Distributed self-organisation in dense wireless ad hoc sensor networks. M.S. thesis, Indian Institute of Science, Chapter 4, Section 4.4.1.Google Scholar
- Aji, S. and McEliece, R. 2002. The generalized distributive law. IEEE Trans. Inf. Theory 46, 2, 325-- 343. Google ScholarDigital Library
- Bettstetter, C. and Eberspaecher, J. 2003. Hop distances in homogeneous ad hoc network. In IEEE Vehicular Technology Conference.Google Scholar
- Costa, J., Patwari, N., and Hero III, A. 2006. Distributed weighted-multidimensional scaling for node localization in sensor networks. ACM Trans. Sensor Netw. 2, 1, 39--64. Google ScholarDigital Library
- Crick, C. and Pfeffer, A. 2003. Loopy belief propagation as a basis for communication in sensor networks. In Uncertainty in Artificial Intelligence, Vol. 18. Google ScholarDigital Library
- De, S., Caruso, A., Chaira, T., and Chessa, S. 2006. Bounds on hop distance in greedy routing approach in wireless ad hoc networks. Int. J. Wirel. Mobile Comput. 1, 2, 131--140. Google ScholarDigital Library
- Ding, Y., Krislock, N., Qian, J., and Wolkowicz, H. 2008. Sensor network localization, Euclidian distance matrix completions, and graph realization. In Proceedings of the Workshop on Mobile Entity Localization and Tracking in GPS-Less Environments. Google ScholarDigital Library
- Dulman, S., Rossi, M., Havinga, P., and Zorzi, M. 2006. On the hop count statistics for randomly deployed wireless sensor networks. Int. J. Sensor Netw. 1, 1--2. Google ScholarDigital Library
- Gupta, P. and Kumar, P. R. 1998. Critical power for asymptotic connectivity in wireless networks. In Proceedings of the Conference on Stochastic Analysis, Control, Optimization and Applications.Google Scholar
- Guvenc, I. and Chong, C. 2009. A survey on TOA based wireless localization and NLOS mitigation techniques. IEEE Comm. Surv. Tutor. 11, 3, 107--124. Google ScholarDigital Library
- He, T., Huang, C., Blum, B. M., Stankovic, J. A., and Abdelzaher, T. 2003. Range-Free localization schemes for large scale sensor networks. In Proceedings of the ACM Annual International Conference on Mobile Computing and Networking (MobiCom'03). 81--95. Google ScholarDigital Library
- Hu, L. and Evans, D. 2004. Localization for mobile sensor networks. In Proceedings of the ACM Annual International Conference on Mobile Computing and Networking (MobiCom'04). 45--57. Google ScholarDigital Library
- Ihler, A., Fisher III, J., Moses, R., and Willsky, A. 2005. Nonparametric belief propagation for self-localization of sensor networks. IEEE J. Select. Areas Comm. 23, 4, 809--819. Google ScholarDigital Library
- Khan, U., Kar, S., and Moura, J. 2009. Distributed sensor localization in random environments using minimal number of anchor nodes. IEEE Trans. Signal Process. 57, 5, 2000--2016. Google ScholarDigital Library
- Kschischang, F., Frey, B., and Loeliger, H. 2001. Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 2, 498--519. Google ScholarDigital Library
- Kuo, J.-C. and Liao, W. 2007. Hop count distance in flooding-based mobile ad hoc networks with high node density. IEEE Trans. Vehic. Technol. 56, 1357--1365.Google ScholarCross Ref
- Kurose, J. and Ross, K. 2010. Computer Networking: A Top-Down Approach Featuring the Internet. Pearson Education, Inc. Google ScholarDigital Library
- Langendoen, K. and Reijers, N. 2003. Distributed localization in wireless sensor networks: A quantitative comparison. Comput. Netw. 43, 4, 499--518. Google ScholarDigital Library
- Li, M. and Liu, Y. 2007. Rendered path: Range-Free localization in anisotropic sensor networks with holes. In Proceedings of the ACM Annual International Conference on Mobile Computing and Networking (MobiCom'07), ACM Press, New York. Google ScholarDigital Library
- Lim, H. and Hou, J. 2005. Localization for anisotropic sensor networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom'05). Vol. 1.Google Scholar
- Miller, L. E. 2001. Distribution of link distances in a wireless network. J. Res. Nat. Instit. Stand. Technol. 106, 2, 401--412.Google ScholarCross Ref
- Nagpal, R., Shrobe, H., and Bachrach, J. 2003. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proceedings of the IEEE International Conference on Information Processing in Sensor Networks (IPSN'03). Google ScholarDigital Library
- Narayanaswamy, S., Kawadia, V., Sreenivas, R., and Kumar, P. R. 2002. Power control in ad hoc networks: Theory, architecture, algorithm and implementation of the compow protocol. In Proceedings of the European Conference on Wireless, Next-Generation Wireless Networks: Techniques, Protocols, Services and Applications.Google Scholar
- Nath, S. and Kumar, A. 2008. Performance evaluation of distance-hop proportionality on geometric graph models of dense sensor networks. In Proceedings of the Performance Evaluation Methodologies and Tools Conference (ValueTools). Google ScholarDigital Library
- Niculescu, D. and Nath, B. 2001. Ad hoc positioning system (APS). In Proceedings of the IEEE Global Communications Conference (GlobeCom'01).Google Scholar
- Niculescu, D. and Nath, B. 2003. DV based positioning in ad hoc networks. Telecomm. Syst. 22, 1, 267--280.Google ScholarDigital Library
- Ozgur, A., Leveque, O., and Tse, D. 2007. Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks. IEEE Trans. Inf. Theory 53, 10, 3549--3572. Google ScholarDigital Library
- Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. Google ScholarDigital Library
- Penrose, M. D. 2003 Random Geometric Graphs. Oxford University Press.Google Scholar
- Ta, X., Mao, G., and Anderson, B. D. O. 2007a. Evaluation of the probability of k-hop connection in homogeneous wireless sensor networks. In Proceedings of the IEEE Global Communications Conference (GlobeCom'07).Google Scholar
- Ta, X., Mao, G., and Anderson, B. D. O. 2007b. On the probability of k-hop connection in wireless sensor networks. IEEE Comm. Lett. 11, 8, 662--664.Google ScholarCross Ref
- Vural, S. and Ekici, E. 2005. Analysis of hop distance relationship in spatially random sensor networks. In Proceedings of the ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05). ACM Press, New York. Google ScholarDigital Library
- Yang, S., Yi, J., and Cha, H. 2007. HCRL: A hop-count-ratio based localization in wireless sensor networks. In Proceedings of the Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON'07).Google Scholar
- Yedidia, J., Freeman, W., and Weiss, Y. 2003. Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millenium. 239--246. Google ScholarDigital Library
- Yedidia, J., Freeman, W. T., and Weiss, Y. 2001. Generalized belief propagation. In Proceedings of the Conference on Neural Information Processing Systems (NIPS'01). MIT Press, 689--695.Google Scholar
- Zorzi, M. and Rao, R. R. 2003. Geographic random forwarding (GeRaF) for ad hoc and sensor networks: Multihop performance. IEEE Trans. Mobile Comput. 2, 337--348. Google ScholarDigital Library
Index Terms
- Theory and algorithms for hop-count-based localization with random geometric graph models of dense sensor networks
Recommendations
Low-cost two-hop anchor node-based distributed range-free localization in wireless sensor networks
ICCSA'10: Proceedings of the 2010 international conference on Computational Science and Its Applications - Volume Part IIIDue to the fact that most of the sensor network applications are based on the location information of sensor nodes, localization is an essential research area. Some localization schemes in the literature require sensor nodes to have additional devices ...
Node localization with AoA assistance in multi-hop underwater sensor networks
AbstractThis paper proposes a novel node localization method in sparse underwater wireless sensor networks (UWSNs) where the locations of only a small number of anchor nodes are available. The proposed method estimates the Euclidean distances ...
An improvement of DV-Hop localization algorithm for wireless sensor networks
An improved DV-HOP localization algorithm is proposed based on the traditional DV-HOP localization algorithm in the paper. There will be a big error that using the nearest anchor node's average hop distance instead of the average hop distance of all the ...
Comments