Approximate convex decomposition based localization in wireless sensor networks

Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu, Chonggang Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

35 Citations (Scopus)


Accurate localization in wireless sensor networks is the foundation for many applications, such as geographic routing and position-aware data processing. An important research direction for localization is to develop schemes using connectivity information only. These schemes primary apply hop counts to distance estimation. Not surprisingly, they work well only when the network topology has a convex shape. In this paper, we develop a new Localization protocol based on Approximate Convex Decomposition (ACDL). It can calculate the node virtual locations for a large-scale sensor network with arbitrary shapes. The basic idea is to decompose the network into convex subregions. It is not straight-forward, however. We first examine the influential factors on the localization accuracy when the network is concave such as the sharpness of concave angle and the depth of the concave valley. We show that after decomposition, the depth of the concave valley becomes irrelevant. We thus define concavity according to the angle at a concave point, which can reflect the localization error. We then propose ACDL protocol for network localization. It consists of four main steps. First, convex and concave nodes are recognized and network boundaries are segmented. As the sensor network is discrete, we show that it is acceptable to approximately identify the concave nodes to control the localization error. Second, an approximate convex decomposition is conducted. Our convex decomposition requires only local information and we show that it has low message overhead. Third, for each convex subsection of the network, an improved Multi-Dimensional Scaling (MDS) algorithm is proposed to compute a relative location map. Fourth, a fast and low complexity merging algorithm is developed to construct the global location map. Our simulation on several representative networks demonstrated that ACDL has localization error that is 60%-90% smaller as compared with the typical MDS-MAP algorithm and 20%-30% smaller as compared to a recent state-of-the-art
Original languageEnglish
Title of host publication2012 Proceedings IEEE INFOCOM, INFOCOM 2012
Number of pages9
Publication statusPublished - 4 Jun 2012
EventIEEE Conference on Computer Communications, INFOCOM 2012 - Orlando, FL, United States
Duration: 25 Mar 201230 Mar 2012


ConferenceIEEE Conference on Computer Communications, INFOCOM 2012
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Approximate convex decomposition based localization in wireless sensor networks'. Together they form a unique fingerprint.

Cite this