Design And Implementation Of A Sensor Network System For Vehicle .

Nodes near evaderteRouobileto MData FilteringPursPursuerArchitecturePursuerLeader Election &Data AggregationuerInterceptionPlanningPath FollowingInterception PlanningPath PlanningPursuitServicesPursuer Position EstimationEntity DisambiguationEstimationServicesEvader Position EstimationPursuerNavigationFig. 2. Logical flow of information in PEG. After the nodes calibratetheir sensors, they listen for events in the network. When events aresensed near several nodes, a leader is elected to aggregate the datainto one packet. This packet is routed to the moving pursuer viamulti-hop routing. After data filtering and interception planning, thepursuer chases the evader.Sensor NetworkArchitectureCalibration &SensingLocalizationLandmark RoutingTree BuildingNetwork ReprogrammingRangingApplicationServicesLeader Election and AggregationConfigNode ManagementNeighborhoodSensing and Entity DetectionHardware cesFig. 3. Hardware and functional division of services. The dottedline separates services running on the pursuer from services runningin the sensor network.III. S YSTEM A RCHITECTURETo provide pursuers with accurate detection eventsquickly and often, we developed services for detection,routing, data processing, and pursuit. We provide a senseof the overall information flow and describe the constituent system services. Power management and securityare beyond the scope of this paper.A. Software ServicesFigure 2 illustrates the information flow from thelower tier sensing field to the higher tier processing unitat the pursuer. The sensor network detects the evader androutes this information to the pursuer, and the pursueracts on this data to intercept the evader. Figure 3 showsthe overall system architecture of the services requiredto implement PEG.When a vehicle is present, the sensing and detection component (Section IV-B) of nearby nodes willtrigger detection events and invoke the leader electionalgorithm (Section IV-D) for data aggregation. The process of leader election is realized over a tuple-spaceneighborhood service (Section IV-C). The elected leaderwill propagate the aggregated data as detections to thepursuers using landmark routing, which operates over asimple tree building mechanism (Section V).When detections reach the pursuer, the pursuer usesan entity disambiguation service to determine the causeof the event: the evader, the pursuer, or noise. Detectionsthat are determined to correspond to the evader are sentto the evader position estimation service. The pursuerposition estimation service uses data from the GPSunit to determine an estimate of the pursuer position.Estimates of the position of the pursuer and evaderare sent to the interception service, which generates ainterception destination for the pursuer. This destinationis processed by the path planning service to generate afeasible route. Finally, the route is submitted to the pathfollowing service that tightly controls the pursuer alongthis route. These mechanisms are further developed inSection VI.Beside the core functionally required for PEG, newsystem services are also implemented to ease the difficulty in managing and configuring the network at thetime of deployment. The Config component allows runtime configuration of system parameters that are usefulfor system tunings. The node management componentis used for node identification, debugging, and networkwide power cycle management. Finally, network reprogramming allows rapid reprogramming the entire systemover the wireless medium, which is valuable for rapidupdate of code image. We discuss these deploymentissues in Section VIII.We originally intended to use a self-localization service to determine each node’s position. This servicewould have used time-of-flight ultrasonic ranging technology with an anchor-based localization algorithm.However, due to sporadic errors, we did not use selflocalization in the live demonstration, and instead hardcoded node positions. For more information on ourlocalization service, refer to work by Whitehouse etal. [18], [19].B. Sensor Tier PlatformThe sensor tier of our system consists of BerkeleyMica2Dot motes [20], a quarter-sized unit with an 8bit 4 MHz Atmel ATMEGA128L CPU with 128 kBof instruction memory and 4 kB of RAM. Its radiois a low power Chipcon CC1000 radio that deliversabout 15 kbit/sec application bandwidth with a maximumcommunication range of around 30 meters using a piano-

ReflectorExposedcomponentsUltrasoundCPU / RadioMag orptionFig. 4. Photograph of a PEG sensor deployed in the field on theday of the demonstration (left), and a schematic of its basic elements(right). The height between the plastic end caps is 3.0 inches (7.6 cm),and the height from the bottom spring base and top of the ultrasoniccone is slight less than twice that distance.the simple higher-tier services shown in Figure 3. TheGPS typically provides estimates every 0.1 seconds withan accuracy of about 0.02 meters. The top speed of therobot is about 0.5m/s, with independent velocity controlfor each wheel. In our deployment, we used one pursuerand one evader, each the same model robot.IV. V EHICLE D ETECTIONDetecting a vehicle in the network begins with a nodegathering and processing data leading up to the formationof a position estimate report. In this section, we showhow a bandwidth analysis of the overall system drivesthe design of our architecture.A. Bandwidth-Driven Designwire antenna placed a few inches from the ground in agrassy field. Each node uses a magnetometer to detectchanges in a magnetic field, presumably caused by anearby moving vehicle. We included a 25kHz ultrasoundtransceiver for time-of-flight ranging. A reflector cone issituated above the transceiver to diffuse the ultrasonicwaves for omni-directional ranging which significantlyreduces the ranging radius to about 2 meters.Figure 4 shows the complete packaging of a sensornode. At the bottom of the node is a base that securesthe node to the ground and extends it a few inchesabove the ground. The battery, voltage conversion board,magnetic sensor, and the Mica2Dot are all protected bythe plastic enclosure. The side of the enclosure has a holethat allows the quarter-wavelength piano wire antenna tobe connected to the Mica2Dot. The only sensor exposedis the ultrasound transceiver at the top, with the conesecurely mounted above it. The package is robust againstimpact from vehicles, and the spring at the base keepsthe node upright even after collisions to elevate the nodea few inches above the ground plane for effective radiocommunication.All nodes at the sensor tier run TinyOS [20], an eventdriven operating system for networked applications inwireless embedded systems. The implementation of allthe core services shown in Figure 3 consumes about60 kB of program memory and about 3 kB of RAM.C. Higher Tier PlatformOur ground robots are essentially mobile off-roadlaptops equipped with GPS. Each robot runs Linux on a266 MHz Pentium2 CPU with 128 MB of RAM, 802.11wireless radio, a 20 GB hard drive, all-terrain off-roadtires, a motor-controller subsystem, and high-precisiondifferential GPS. This platform is sufficient to executeWe design our sensor network to provide full, redundant sensor coverage – for sensors placed in a grid,a vehicle excites at least four and up to nine sensors.From this coverage requirement, we design the rest ofthe detection system with an understanding of the impactof low-level decisions on regional bandwidth limits.Presuming a local aggregate bandwidth of forty 36byte packets per second, a single node can provide upto four reports per second before a region of nine nodessaturates the shared channel. If each node sends thesedetection events, the local channel will be saturatedleaving no bandwidth for other communications suchas routing these readings to the pursuer. Additionally,as more vehicles are added to the system, routing thedata will increasingly tax the bandwidth of the system.Clearly, we must use some techniques to conserve bandwidth.We use local aggregation to reduce many detectionevents into one position estimate report. We allocatehalf the total bandwidth for exchanging local detection reports and the remaining bandwidth for systemwide behaviors such as routing position estimates topursuers. Even though sharing local detections uses asignificant portion of the local bandwidth, the pursuerstill receives frequent position updates. We decomposethis overall process into three distinct phases: calibrationand sensing, local detection reports, and leader electionand position estimation.B. Calibration and SensingThe magnetometer measures the entire magnetic environment. This includes static structures such as theEarth’s magnetic field and other metal in the surroundings. To detect changes in the magnetic field causedby a moving vehicle, this static environment must be

accounted for in each node’s measurements. Each nodebiases each reading given a moving average of the sensorreadings. This sets a minimum detectable speed on avehicle, because a sufficiently slowly moving object willbe indistinguishable from the static environment.One interaction that we did not expect is a relationshipbetween the radio communication and the magnetometer.Because of the proximity of the radio chip and themagnetometer chip, which is in part a result of the smallpackage design but also exacerbated by our hardwaredesign, radio transmissions excite significant readingsfrom the magnetometer. As a workaround, we invalidatemagnetometer readings for a short period whenever aradio packet is sent or received at the node.C. Local Detection ReportsTo decide if a node should share its calibrated readingwith its neighbors, the node compares the 1-norm ofits magnetic reading against a preset threshold value.If the detected value exceeds this threshold, the nodesends a message including the magnetic magnitude andits own (x, y)-position in meters. To limit a node’s localdetection report rate to 2 packets per second, each nodeis subject to a reading timeout of 0.5 seconds duringwhich it is not allowed to share a new reading.To share data among a neighborhood of nodes, weevolved a new programming primitive called Hood [21].A neighborhood in Hood defines a set of criteriafor choosing neighbors and a set of variables to beshared. The neighborhood membership, data sharing,data caching, and messaging is managed by the Hoodabstraction, allowing the developer to focus on theproperties of a neighborhood instead of its mechanics.Hood exploits the cheap broadcast mechanism of asensor network to allow asymmetric membership – anode broadcasts changes to its neighborhood values anddoesn’t know or care what other nodes consider it amember, which is different from the group collaboration work found in [9], [10]. Hood is well suitedfor unreliable communication channels such as those insensor networks, and defers concerns of reliability andconsistency to the application level.For PEG, we created a MagHood that manages themessaging and caching of local detection reports andprescribes the neighborhood membership criteria. Because the magnetometer neighborhood represents a localphysical relationship, and because radio connectivitydoesn’t have a clean relationship with respect to physicaldistance, membership in the neighborhood is restrictedto only those nodes within 3 meters. And, similar to thereport timeout, readings are invalidated after timeout of0.5 seconds, which sets a time window on the validityof a neighbor’s reading.D. Leader Election and Position EstimationWe cast leader election as primarily a bandwidthreduction technique and relax the usual requirement ofcorrelating a single leader with a single entity, unlike[9], [10] where vehicle classification is done on thesensor node. High level processing on the pursuersimposes model constraints to correlate position estimateswith individual entities. This decomposition allows us toconstruct a significantly more simple and robust leaderelection protocol.Using MagHood, each node gains a view of the recentdetection reports from nodes in its neighborhood. At thispoint, the leader election protocol requires no additionalcommunication – a node elects itself leader if it has themaximum magnetometer magnitude among the nodes inits neighborhood. This lightweight mechanism embodiesthe idea of loose consistency: in the worst case, everynode that detects the location of a vehicle reports it.The pursuer receives reports about all position estimates in the network – those caused by the evader,by itself, or by noise. Even with this policy, redundantleaders for a single object are the exception not the rule,because leadership changes smoothly over time given thephysical interactions. Additionally, this design implicitlysupports multi-object tracking by providing all the datanecessary for the pursuer to do centralized filtering andcorrespondence.The position estimate report contains the (x, y)position calculated as a center of mass, the total numberof nodes contributing to the report, and the sum ofthe detection magnitudes. Similar to previous timeouts,a node is only allowed to become leader and send aposition estimate report at most every 0.5 seconds. Thisestimated position is again a loosely consistent value– instead of using a time synchronization service toguarantee that all readings happen within a strict epoch,the cache timeout establishes a notion of a weak epoch.Within each weak epoch, a node elects itself leaderthe instant it determines it has the largest detectionmagnitude. As an alternative, if a node would havewaited a period of time for additional readings, thereexist certain vehicle paths that prevent any node frombecoming a leader, which would produce no positionestimates for the pursuer. Furthermore, this protocolensures that a node can become a leader if its detectionexceeds the threshold, meaning that the maximum speed

of the vehicle is only a function of the properties of thesensor and the allocated bandwidth for position reports.V. ROUTINGThe primary routing requirement in PEG is to deliverthe evader detection events, as sensed by the network,to the mobile pursuers. That is, we must route packetsfrom many sources to a few mobile destinations. Thisdiffers from the typical many-to-one data collectiontraffic model found in other sensor network applications[22], [23], [24]. However, it resembles some of the workfound in the mobile computing literature, which providesdifferent approaches to support this mobile routing service. In this section, we first explore these approachesand then discuss a simple and efficient landmark routingapproach to arrive with a solution, which is potentiallyapplicable to systems other than PEG.A. Design ApproachesOne design approach is to treat the entire network andthe mobile pursuers as one ad-hoc mobile system, anddeploy well-known mobile routing algorithms, such asDSR, AODV, and TORA [25], [26], [27], which requireO(N ) of communication complexity to provide an anyto-any routing service. These protocols are designed tosupport any pairs of independent traffic flows while thetraffic in PEG is correlated and directed only to a fewmoving end points (the pursuers).Another approach is to decouple the network from themobile pursuers and exploit the static network topologyto decrease the communication complexity for routing.This resembles the home-agent work found in mobilecomputing [28], where every pursuer is assigned a homeagent. For example, recent work supports group communication among a set of moving agents over a sensornetwork in a bounding box [29]. It assumes that anyto-any routing comes free by using geographical routingand maintains a horizontal backbone to support communication among moving agents within the bounding box.The communication complexity depends on the overheadof backbone maintenance and home agent migrationfrequency.For efficiency and simplicity, the approach we usealso exploits the static network topology, but we do notassume any geographical routing support or grid locationinformation as in [30]. We use a variant of landmarkrouting [31] to split the many-to-few routing probleminto two subproblems: many-to-landmark and landmarkto-few. Landmark routing is a simple mechanism thatuses a known rendezvous point to route packets frommany sources to a few destinations. For a node in thespanning tree to route a detection event to a pursuer,it first sends a message up a spanning tree to the rootnode, the landmark. Then the landmark forwards themessage to the pursuer. The original landmark paperdiscusses a hierarchy of landmarks for scalability. In thiswork, we only consider a single landmark. Landmarkrouting results in longer routing paths as traffic must gothrough the landmark, which hurts latency, but requiresless control bandwidth to maintain routes to the movingtarget than other protocols such as AODV.B. Building Good TreesFor many-to-landmark routing, we rely on a spanningtree rooted at the landmark. All packets are forwardedalong the tree towards the landmark. A common approach to building a spanning tree is to flood the networkwith a beacon, and each node marks its parent in the treeas the first node from which it receives the beacon, andthen rebroadcasts the beacon. This approach of floodingthe network and routing using the reversed paths is usedin ad-hoc routing algorithms such as AODV [26] andDSR [25] to build a topology quickly and trade offoptimality for handling mobility.Such a flooding process must address two potential problems: quality route selection and the broadcaststorm problem [32]. The routing protocol must avoidselecting bad links for routing; in particular, asymmetricconnectivity should be avoided since the reverse pathsare used for routing. Route selection solely using hopcount cannot address these issues. The second issue,broadcast storms, occurs when many nodes receive abeacon simultaneously and attempt to rebroadcast thebeacon immediately. As a result, a storm of packetcollisions is created and significant message loss wouldoccur, which leads to an ill-formed topology containingmany back edges. Back edges occur when nodes missa beacon message because of collisions, but later overhear it from nodes further down the tree. Back edgescreate unnecessarily long routes. Empirical data in [33]provides evidence of these issues.Our first challenge is route selection. A node mustconsider both the link quality and tree depth of thepotential parent. Without any rapid link estimation mechanism, we rely on the received signal strength indicator(RSSI). Recent studies in [34] and [35] show that RSSIis not always a good predictor of link quality. However,we can exploit spatial information to our advantageto rely on RSSI values. With all nodes on roughlyon a grid configured to transmit at the same power

18171615141312y position (meters)and the fact that signal strength decays at least 1/d2when close to the ground, it is possible to use RSSIthreshold filter to scope the neighborhood relative tothe physical distance. By empirically measuring therelationship between link reliability and RSSI valuesamong nodes at different grid distances beforehand, wedetermine a high confidence RSSI value for the entirenetwork that maximizes communication distance whilereliably preserving bidirectional link reachability for ourreverse path routing. A node only accepts a message ifits RSSI value is greater than the threshold, even if itwas able to properly decode the message. The routinglayer can be a simple algorithm that selects the shortesthop-count parent that passed the RSSI filter. Section VIIpresents measurements of the end-to-end reliability ofthe routing paths discovered by this approach.The second challenge is to alleviate the broadcaststorm problem. We used a time-delayed back-off thatadapts to the observed cell density. Broadcast stormsoccur because several nodes simultaneously attempt torebroadcast the beacon. Instead, if each node waits arandom time before re-broadcasting the beacon, thennetwork congestion decreases. With random back-off,the number of potential wait times should be proportional to the number of nodes in a radio cell; as nodedensity increases, nodes must wait longer periods oftime. Choosing the maximum wait time, then, requiresknowledge of the density. An alternative idea is toemploy a more adaptive technique. Upon the receptionof a broadcast message, each receiver starts a timer tofire in a random amount of time less than R. Everytime the node receives a broadcast message before itstimer expires, it resets the timer to fire in a new randomtime. Thus, the R interval from which nodes wait issignificantly smaller than in the naive protocol. The totalwait time is now adaptive and inversely proportional tothe radio cell density, which is the number of times thesame broadcast message is heard. In both sparse anddense networks, propagation within local cells finishesin R · n/2 time, where n is the cell density.One typical spanning tree is in Figure 5. The datawas collected from 100 mica2dots with 2m spacing. Thelandmark is near the center of the field, at position (8,8).The tree has depth three, considerably less than if gridrouting were used. Four nodes did not join the spanningtree because they were broken; Section VIII addressesbreakage. Additionally, the parents of most nodes arephysically closer to the landmark. In those cases wherethis is not true, such as at (0

computing resources. This paper describes the design, implementation, and experience with PEG. Our main contributions are: We describe the design and implementation of PEG, a networked system of distributed sensor nodes that detects an evader and aids a pursuer in capturing the evader. We employ whole-system analysis and utilize spa-