Border landmark selection and applications in self-configurable wireless networks

In this paper, we propose three algorithms for border landmark selection, namely the convex hull-based (CHB) algorithm, the center node elimination (CNE) algorithm, and the hierarchy-structured (HS) algorithm. CHB works perfectly in theory and provides a deep insight into the landmark selection problem. At the same time, it is noticed that CHB is centralized and sensitive to errors in distance estimation. The CNE algorithm is a distributed approach, devised to gradually exclude the nodes in the ldquocenterrdquo of the network till the desired number of nodes left, which are employed as landmarks. While CNE works effectively in a small network, its high order computation complexity and communication overhead may eventually lead to scalability problem when it is applied in very large networks. To address this problem, we propose the HS algorithm for striking the balance between accuracy and complexity/overhead. In HS, we establish a hierarchical structure with multiple layers, and apply the CNE algorithm in an appropriate layer to identify an initial set of candidate nodes. The outcomes are then rectified through a recursive process, yielding the final landmarks. Three applications, including coordinates establishment, border detection, and landmark-based routing in general networks without location information, are introduced based on the selected landmarks. We carry out extensive simulations to compare the performance of our landmark selection algorithms and demonstrate their effectiveness in all of the applications.