An Approximate Convex Decomposition Protocol for Wireless Sensor Network Localization in Arbitrary-Shaped Fields

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)


Accurate localization in wireless sensor networks is the foundation for many applications, such as geographic routing and position-aware data processing. In this paper, we develop a new localization protocol based on approximate convex decomposition (ACDL), with reliance on network connectivity information only. ACDL can calculate the node virtual locations for a large-scale sensor network with a complex shape. We first examine one representative localization algorithm and study the influential factors on the localization accuracy, including the sharpness of the angle at the concave point and the depth of the concave valley. We show that after decomposition, the depth of the concave valley becomes irrelevant. We thus define the concavity according to the angle at a concave point, which reflects 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 section of the network, an improved 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. Besides, by slight modification on the third step, we propose a variant of ACDL, denoted by ACDL-Tri, which is fully distributed and scalable while the localization accuracy is still comparable. We finally show the efficiency of ACDL by extensive simulations.
Original languageEnglish
Article number7000585
Pages (from-to)3264-3274
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number12
Publication statusPublished - 1 Dec 2015


  • approximate convex decomposition
  • Localization
  • wireless sensor networks

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'An Approximate Convex Decomposition Protocol for Wireless Sensor Network Localization in Arbitrary-Shaped Fields'. Together they form a unique fingerprint.

Cite this