[attachment=15424]
Abstract:
Secure distance-based localization in the presence of cheating beacon (or anchor) nodes is an important problem in mobile wireless ad hoc and sensor networks. Despite significant research efforts in this direction, some fundamental questions still remain unaddressed: In the presence of cheating beacon nodes, what are the necessary and sufficient conditions to guarantee a bounded error during a two-dimensional distance-based location estimation? Under these necessary and sufficient conditions, what class of localization algorithms can provide this error bound? In this paper, we attempt to answer these and other related questions by following a careful analytical approach. Specifically, we first show that when the number of cheating beacon nodes is greater than or equal to a given threshold, there do not exist any two-dimensional distance-based localization algorithms that can guarantee a bounded error. Furthermore, when the number of cheating beacons is below this threshold, we identify a class of distance-based localization algorithms that can always guarantee a bounded localization error. Finally, we outline three novel distance-based localization algorithms that belong to this class of bounded error localization algorithms. We verify their accuracy and efficiency by means of extensive simulation experiments using both simple and practical distance estimation error models.
INTRODUCTION:
LOCALIZATION or location discovery in distributed wireless networks is the problem of determining the location, with respect to some local or global coordinate system, of a (mobile) device in the network in an efficient and accurate fashion. Distributed localization protocols in such networks can be broadly classified into range-based and range-free techniques Range-based techniques can be further classified into two broad categories, viz., 1) Beacon-based techniques and 2) Beacon-free techniques. In this work, we focus primarily on beacon-based localization algorithms. Beacon-based algorithms such as require the presence of special nodes, called beacon or anchor nodes, which know their own location and are strategically placed in the network. Other nodes first compute the distance (or angle) estimates to a set of neighboring beacons and then estimate their own location using basic trilateration (or triangulation). The working of a two-dimensional beacon-based localization scheme using distance estimates to neighboring beacons is shown in Fig. 1a. In Fig. 1a, nodes B1, B2, B3, and B4 located at positions respectively, act as beacon nodes. The target node T estimates,respectively, to these beacon nodes and computes its own location by trilateration. Efficient techniques for estimating distances such as Received Signal Strength Indicator Time of Arrival and Time Difference of Arrival) exist and have been successfully used in the various beacon-based localization protocols listed above.
Although beacon-based techniques are very popular in most wireless systems, they have one shortcoming. Most beacon-based techniques in the literature assume that the nodes acting as beacons always behave honestly. It is not surprising that beacon-based methods perform well when all the beacon nodes are honest. But their accuracy suffers considerably in the presence of malicious or cheating beacon nodes. Beacons can cheat by broadcasting their own locations inaccurately or by manipulating the distance estimation process, thus, adversely affecting the location computation by the other nodes. This is depicted in Fig. 1b. In this figure, we can see that beacon nodes B1, B2, and B4 behave honestly, whereas beacons B3 and B0 3 cheat. This causes the target node T to compute its location incorrectly as instead of . Earlier research efforts in securing distance-based localization techniques have focused on either removing this (over)dependence on beacon nodes or on minimizing the effects of malicious beacons during localization. But before delving into the possible solutions for secure localization, we feel that there is a need to address the following questions that have been ignored by earlier research efforts: Under what condition(s) do there exist algorithms that can overcome the cheating effect of 810 IEEE TRANSACTIONS ON MOBILE COMPUTING, malicious beacons? How do we determine these algorithms when these condition(s) are satisfied, if at all? What kind of guarantee on the solution quality (in terms of bounds on the error in localization) can such algorithms provide? None of the research efforts undertaken previously provide an answer to all these questions. study the problem of distance-based localization from a theoretical standpoint and provide conditions for unique network localization using graph rigidity theory, but their results assume noncheating beacon nodes.
What has been missing in the literature is a comprehensive theoretical framework for studying the hardness and feasibility of the distancebased localization problem in the presence of cheating beacons. A systematic analytical study would not only help in designing efficient algorithms to solve this problem, but would also help in deriving performance bounds guaranteed by these algorithms, thus, facilitating an effective comparative analysis. In this paper, we attempt to fill this gap between theory and practice by first establishing the necessary and sufficient conditions for the problem of secure distance-based localization in the presence of cheating beacon nodes and then outlining a class of algorithms that can always guarantee a bounded localization error. Specifically, we make the following contributions: First, we prove that if the number of malicious beacons is greater than or equal , where n is the total number of beacons providing distance information, then no algorithm can guarantee a bounded localization error for all cases. In other words, as long as the above inequality holds, any distance based algorithm will fail to estimate the target location within a small error bound for at least one scenario or setup of beacons. Next, we show that there exist algorithms that provide a guaranteed degree of localization accuracy (for all the cases), if the number of malicious beacons is less than or equal to. These two inequalities are also referred to as the necessary and sufficient conditions for robust localization. Given the above conditions, we define a class of distance based localization algorithms that can always localize with a bounded error. We transition from theory to practice by proposing three illustrative algorithms that belong to this class of robust distance-based algorithms.
A systematic analytical study would not only helping designing efficient algorithms to solve this problem, but would also help in deriving performance bounds guaranteed by these algorithms, thus, facilitating an effective comparative analysis. In this paper, we attempt to fill this gap between theory and practice by first establishing the necessary and sufficient conditions for the problem of secure distance-based localization in the presence of cheating beacon nodes and then outlining a class of algorithms that can always guarantee a bounded localization error. Specifically, we make the following contributions: First, we prove that if the number of malicious beacons is greater than or equal to n_2 2 , where n is the total number of beacons providing distance information, then no algorithm can guarantee a bounded localization error for all cases. In other words, as long as the above inequality holds, any distance based algorithm will fail to estimate the target location within a small error bound for at least one scenario or setup of beacons. Next, we show that there exist algorithms that provide a guaranteed degree of localization accuracy (for all the cases), if the number of malicious beacons is less than or equal to n_32 . These two inequalities are also referred to as the necessary and sufficient conditions for robust localization. Given the above conditions, we define a class of distance based localization algorithms that can always localize with a bounded error. We transition from theory to practice by proposing three illustrative algorithms that belong to this class of robust distance-based algorithms. the, uses an exhaustive search strategy to provide good localization accuracy with a polynomial (cubic) runtime complexity(in terms of the number of available beacons) in the worst case. But in practice, the Polynomial-Time algorithm runs very inefficiently. To overcome this problem, we propose two other algorithms. These algorithms use simple heuristics to securely compute locations and have much better execution efficiency. Finally, we verify the performance of these algorithms through extensive simulation experiments and present a detailed comparative analysis based on the simulation results. We also extend the existing localization framework to include more practical distance estimation error models and also study their effect on the accuracy of good localization