| Recent technological advances have fostered the emergence of small, low-power devices that integrate micro-sensing and actuation with on-board processing and wireless communications capabilities. Through distributed coordination, pervasive networks of micro-sensors and actuators are expected to revolutionize the ways in which we understand and construct complex physical systems. Fundamental to such coordination is localization, or the ability to establish spatial relationships among objects.; In this dissertation, we address the challenges involved in localization for very large, ad hoc deployed sensor networks. Although several localization technologies have been proposed in the past few years, none Currently satisfies all our requirements because no single localization system is simultaneously scalable, ad hoc deployable and accommodating of the hardware constraints of very small devices. Our thesis is that all these issues can be solved simultaneously by a self-configuring localization system that autonomously adapts to its environmental dynamics. Our approach is based on localized adaptive algorithms that self-configure to exploit both the local processing on each sensor node, as well as the redundancy across densely-deployed sensor nodes.; First, to accommodate device constraints, we adopt a low cost, hardware-independent localization approach for very small devices that leverages the existing radio (RF) communications capabilities of such devices and does not require any other sensors.; Second, to scale to very large sensor networks, we develop a decentralized, self-localization methodology for devices. Instead of relying on a central server to compute their positions, devices themselves perform a localized location computation based on radio connectivity constraints to a small number of nearby beacons (nodes with known positions), obtained by listening to radio broadcast advertisements of beacons.; Third, we need to ensure a uniform localization granularity in dynamic, unpredictable environments with numerous radio propagation vagaries. One solution to this problem is to extensively instrument and model the environment, a priori. Unfortunately, this approach does not scale well. Instead, we advocate and develop a self-configuring mechanism in which beacons themselves measure and adapt to their environment and availability of neighboring beacons.; Finally, we quantitatively analyze the impact of beacon density on localization. We show that proximity based localization using only local information saturates at a threshold beacon density μthresh. We develop various self-configuring algorithms for incremental beacon placement for sparse beacon deployment. For dense beacon deployment, it is desirable to keep the operational beacon density close to μthresh to reduce the probability of self-interference amongst beacons and to conserve energy. We develop a parameterized algorithm (tunable according to radio parameters) to adjust the duty cycle of beacons based on the availability of other beacons in the neighborhood to realize a low operational density.; These techniques form the bases of our self-configuring localization system. We have implemented it as a user-level library on two test-beds, Radiometrix RPC-418 radios, and motes with RFM radios. We evaluate and demonstrate the effectiveness of our localization system in terms of the performance of the basic localization algorithms, as well as the beacon placement techniques to adapt it to noisy environments. |
