Project Proposal:Mobility, Navigation and LocalizationPrabal Dutta and Sarah BergbreiterCS294-1: Deeply Embedded Network Systems{prabal,sbergbre}@eecs.berkeley.edu1 IntroductionWe propose to study the symbiotic relationship between mobility, navigation,and localization in the context of wireless sensor networks and mobile objects.We observe that mobility can aid in network node localization and that oncelocalized, the network nodes can localize and track a mobile object (robot) andguide its navigation. Our motivation, and the ultimate goal of this work, is torealize the following scenario. A set of sensor networks nodes are dropped ontoa field at unknown locations. A friendly (or unfriendly) mobile object travelsthrough the sensor network in a structured (or random) walk. The network nodesdetermine their own locations by estimating the range to this mobile object in acoordinated fashion and applying a transform to these range estimates to yieldthe node positions in some global coordinate frame. Once localized, the nodesmay multilaterate the location of the mobile object and guide its motion tolocations and events of interest within the sensor network.2 Range EstimationRobust range estimation is essential to localization of either the nodes or robots.Unfortunately, range estimation has proven to be difficult in sensor networksand affordable/precise general solutions do not yet exist. Hence, we view rangeestimation as high risk and critical path, and propose to invest our early ef-forts in this area. As a risk mitigation strategy, we will investigate two differenttechniques for range estimation: ultrasonic and magnetic.Ultrasonic ranging would leverage work from the Calamari project and wouldinvolve integrating the Mica2Dot ultrasound boards used in the DARPA midtermdemonstration and the CotsBots robots previously developed by one of the au-thors. Magnetic ranging would leverage concurrent work on creating an empiricalsensor model being performed at Intel Research Berkeley by one of the authors.In either case, We would make some simplifying assumptions to make the rang-ing problem tractable in the available timeframe. For example, we assume thatonly one robot is present at a time and that the robot’s size is negligible. In thegeneral case, we could not make these assumptions.3 LocalizationThere are two aspects of localization that are relevent for our research. The firstcase is the localization of the network nodes (sensors) such that nodes can deter-mine their coordinates. Depending on the ranging techniques that are employed,the network node localization problem may be able to leverage earlier work likeCalamari. On the other hand, a more interesting research problem may be to usea mobile object to localize the nodes. Hence, we describe below the mobile objectbased approach to localizing the nodes. We then assume the node positions areknown and review localization of a mobile object via multilateration.3.1 Network No desGiven a ranging technology that allows three independent sensor nodes to rangethe same mobile object simultaneously, we now propose our localization ap-proach. Consider a single mobile object or target1traversing through a sensornetwork as shown in Figure 1.r1,3r2,3r3,3r1,1r2,1r3,1r1,2r3,2r2,2N1N2N3t1t2t3Trajectory ofmobile objectFig. 1. The trajectory of a target (yellow dot) and its distance rn,tfrom three sensornodes at three points in time, where n is one of N1,N2,N3,andt is one of t1,t2,t3.The positions of the three nodes N1,N2, and N3are initially unknown and werefer to these nodes as the unknown nodes. Each of these unknown nodes is ableto determine the distance to the target at three distinct times t1,t2, and t3.Letthe three nodes and the location of the target at the three times be the six verticesof a 2-dimensional geometric structure with nine edges given by the ranges rn,t.Our algorithm would determine the distance di,jbetween any pair of nodes Niand Njthat satify our initial assumption. Once the set of inter-node distancesare calculated, multidimensional scaling or some similar transform can be used1We refer to the mobile object as the target since it is the target of the ranging.to convert the distance estimates to a coordinate system. We are uncertain aboutthe specifics of the proposed algorithm and the development of the algorithm isitself an important component of the project effort. There are two key anticipatedchallenges. The first challenge is proving that the planar geometric structurewhose six vertices are defined by the location of the three unknown nodes andof the target at the three times, and whose edges are the nine range estimatesis rigid, non-deformable, and unique. Integrating error from the range estimatesinto this algorithm will also be crucial. The second challenge is devising thealgorithms that allow inter-node distances to be computed from the set of rangeestimates.3.2 Mobile RobotsLocalizing the position of a mobile robot based on distance or range measure-ments from three or more spatially-distributed sensors is a familiar multilat-eration problem. We will restrict our analysis to two dimensions although theapproach can be generalized easily to three dimensions. A single range measure-ment, r, restricts the target’s location to a circle of radius r centered at thesensor. Similarly, if a second sensor can provide a range measurement as well,then the target’s position is restricted to one of the two points where the twocircles intersect, unless of course the circles do not intersect or the target fallson the line connecting the two sensors. If a third sensor can provide a rangemeasurement, then the target’s position can be narrowed to just one position.With only two dimensions, three range estimates will exactly determine the tar-get’s location and four or more range estimates will overdetermine the solution.However, given the error inherent in the sensors, more range estimates will likelyimprove robot localization.4 NavigationOnce the problems of node and robot localization are solved, we can turn ourattention to the problem of navigation. By navigation, we mean the guidanceof a robot from one location to another. In one view of navigation, we mayenvision that a robot has notions of its current and future locations, and cancompute and follow a trajectory that will allow it to get from “here” to “there.”A
View Full Document
Unlocking...