Abstract
Localization, an important challenge in wireless sensor networks, is the process of sensor nodes self-determining their position. The difficulty encountered is in cost-effectively providing acceptable accuracy in localization. The potential for the deployment of high density networks in the near future makes scalability a critical issue in localization. In this paper we propose Cluster-based Localization (CBL), which provides effective localization suitable for large and highly-dense networks. CBL utilizes both a computationally-intensive localization technique (non-metric multidimensional scaling (MDS)) and a less intensive trilateration to achieve balance between performance and cost. Clustering is utilized to select a subset of nodes to perform MDS and then extend their localization to the remaining network. Besides providing scalability clustering overcomes local irregularities and provides good accuracy even in irregular networks with or without obstacles. Simulation results illustrate that CBL reduces both computation and communication, while still yielding acceptable accuracy.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Chan, H., Luk, M., Perrig, A.: Using Clustering Information for Sensor Network Localization. In: Prasanna, V.K., Iyengar, S.S., Spirakis, P.G., Welsh, M. (eds.) DCOSS 2005. LNCS, vol. 3560, pp. 109–125. Springer, Heidelberg (2005)
Shang, Y., Ruml, W.: Improved MDS-based localization. In: INFOCOM, vol. 4, pp. 2640–2651 (2004)
Akyildiz, I., Su, W., Sankarasubramaniam, Y., Cayirci, E.: A survey on sensor networks. IEEE Communications Magazine, 102–114 (2002)
Shih, E., Cho, S., Ickes, N., Min, R., Sinha, A., Wang, A., Chandrakasan, A.: Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks. In: MobiCom (2001)
Niculescu, D., Nath, B.: Ad hoc positioning system (APS). In: GLOBECOM, vol. 5, pp. 2926–2931 (2001)
Savarese, C., Rabaey, J., Beutel, J.: Locationing in distributed ad-hoc wireless sensor networks. In: ICASSP, vol. 4, pp. 2037–2040 (2001)
Yao, Q., Tan, S., Ge, Y., Yeo, B., Yin, Q.: An area localization scheme for large wireless sensor networks. In: VTC, vol. 2, pp. 2835–2839 (2005)
Sichitiu, M., Ramadurai, V.: Localization of wireless sensor networks with a mobile beacon. In: MSN, pp. 174–183 (2004)
Sun, G., Guo, W.: Comparison of distributed localization algorithms for sensor networks with a mobile beacon. In: ICNSC, vol. 1, pp. 536–540 (2004)
Patro, R.: Localization in wireless sensor network with mobile beacons. IEEE Convention of Electrical and Electronics Engineers in Israel, 22–24 (2004)
Li, X., Shi, H., Shang, Y.: A partial-range-aware localization algorithm for ad hoc wireless sensor networks. In: LCN, pp. 77–83 (2004)
Doherty, L., Pister, K., El Ghaoui, L.: Convex position estimation in wireless sensor networks. In: INFOCOM, vol. 3, pp. 1655–1663 (2001)
Bergamo, P., Asgari, S., Wang, H., Maniezzo, D., Yip, L., Hudson, R., Yao, K., Estrin, D.: Collaborative sensor networking towards real-time acoustical beamforming in free-space and limited reverberance. TMC 3(3), 211–224 (2004)
Galstyan, A., Krishnamachari, B., Lerman, K., Pattem, S.: Distributed online localization in wireless sensor networks using a moving target. In: IPSN, pp. 61–70 (2004)
Coxon, A.: The Users Guide to Multi Dimensional Scaling. Heinemann Educational Books (1982)
Ji, X., Zha, H.: Robust sensor localization algorithm in wireless ad hoc sensor networks. In: INFOCOM, pp. 527–532 (2003)
Eren, T., Whiteley, W., Belhumeur, P.: Further results on sensor network localization using rigidity. In: EWSN, pp. 405–409 (2005)
Liu, K., Wang, S., Ji, Y., Yang, X., Hu, F.: On connectivity for wireless sensor networks localization. In: IWCCC, vol. 2, pp. 879–882 (2005)
Perkins, D., Tumati, R.: Reducing localization errors in sensor ad hoc networks. In: IPCCC, pp. 723–729 (2004)
Savarese, C., Rabaey, J., Langendoen, K.: Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In: USENIX Annual Technical Conference, pp. 317–327 (2002)
Karalar, T., Yamashita, S., Sheets, M., Rabaey, J.: A low power localization architecture and system for wireless sensor networks. In: SIPS, pp. 89–94 (2004)
Ahmed, A., Hongchi, S., Shang, Y.: Sharp: A new approach to relative localization in wireless sensor network. In: ICDCS, pp. 892–898 (2005)
Shang, Y., Ruml, W., Zang, Y., Fromhertz, M.: Localization from mere connectivity. In: MobiHoc, Annapolis, MD, pp. 202–212 (2003)
Shang, Y., Meng, J., Shi, H.: A new algortihm for relative localization in wireless sensor networks. In: IPDPS (2004)
Morrison, A., Ross, G., Chalmers, M.: Fast multidimensional scaling through sampling, springs and interpolation. Information Visualization 2, 68–77 (2003)
ns-2, discrete event simulator (2006), URL: http://www.isi.edu/nsnam/ns/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Medidi, M., Slaaen, R.A., Zhou, Y., Mallery, C.J., Medidi, S. (2006). Scalable Localization in Wireless Sensor Networks. In: Robert, Y., Parashar, M., Badrinath, R., Prasanna, V.K. (eds) High Performance Computing - HiPC 2006. HiPC 2006. Lecture Notes in Computer Science, vol 4297. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11945918_50
Download citation
DOI: https://doi.org/10.1007/11945918_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68039-0
Online ISBN: 978-3-540-68040-6
eBook Packages: Computer ScienceComputer Science (R0)