IntroductionCanonical ApplicationsCommunication PatternsDisseminationCollectionPoint-to-PointAggregationCoordination PatternsTime SynchronizationLocalizationLeader ElectionEnergy ManagementOther Coordination PatternsConclusionReferencesCommunication and Coordination Patterns in Sensor Networks- CS294-4 Project Report, Spring 2007 -Prabal Dutta and Jay TanejaComputer Science DivisionUniversity of California, BerkeleyBerkeley, California 94720{prabal,taneja}@cs.berkeley.edu1 IntroductionThe research community has justified considerable re-search efforts in the area of sensor networks based on theconjecture that sensor networks require fundamentally dif-ferent communication and coordination patterns than tradi-tional IP networks. An effort to codify the nature of thesepatterns has already begun in many aspects of the still de-veloping field of sensor networks, including software de-sign [23], network layer formation [7], and system designprinciples [6]. As this trend continues and the field matures,the key services for communication and coordination willcontinue to emerge, allowing for this fledgling class of net-works to have an overall architecture [3] that imitates, butis vastly different than traditional networking and distributedsystems. In this paper, we survey fielded applications anddistill the actual communications and coordination patternsin use. By performing this study, we validate our hypothesisthat a small set of services is sufficient to meet the needsof most applications. Since we recognize that only timecan definitively determine the actual services that becomewidespread, we also examine less widely used communica-tion and coordination services, as they may become morecommon in future applications.2 Canonical ApplicationsOur survey of sensor networks yielded four broad appli-cation classes: data collection, event detection, object track-ing, and wireless control, but in this section we focus onthe first two classes and leave the third class for treatmentelsewhere, and skip the last class altogether. The rationaleis the majority of sensornet applications are either data col-lection or event detection, and a handful are object tracking(largely DARPA-funded target tracking), while the wirelesscontrol applications are primarily industrial (and largely un-documented). Table 1 lists a number of the key differencesbetween data collection and event detection.The differences in the requirements of data collection andevent detection lead to differences in the space, time, andmessage complexity of the algorithms used to realize theseapplications. Increases in complexity may result in corre-sponding increases in energy usage, generally considered themost precious resource in these systems.Signal Reconstruction vs Signal Detection: Theessence of data collection is information and communica-Data Collection Event DetectionSignal Reconstruction Signal DetectionReconstruction Fidelity Detections, False AlarmsData-centric Metadata-centricData-driven Messaging Decision-driven MessagingHigh-latency Acceptable Low-latency RequiredPeriodic Traffic Bursty TrafficStore & Forward Messaging Real-Time MessagingAggregation Fusion, ClassificationOmnichronic Rare, Random, Short-livedAbsolute Global Time Relative Local TimeTable 1. A summary of the differences between data col-lection and event detection applications.tions theory which seeks to centrally reconstruct a distributedspace-time varying field. The essence of event detection isstatistical detection theory that seeks to decide among two ormore hypotheses. Assuming that data collection is periodic,that the data change with some uncertainty, and that eventsare rare, it would appear that data collection has a greatermessage complexity than event detection as measured by in-formation communicated per unit time.Reconstruction Fidelity vs Detections, False Alarms:Important performance metrics for data collection includethe accuracy and precision of the reconstructed field. Im-portant performance metrics for event detection include theprobabilities of detection and false alarm. Greater fidelitywould appear to require greater space and message complex-ity. Improved detection and false alarm rates would appearto require greater space (storing more samples or interme-diate results of computations), time (more complex com-putations), or message (comparing detection decisions withneighbors) complexity.Data-centric vs Metadata-centric: Data collection usu-ally focuses on sampling directly measurable phenomenalike temperature, pressure, humidity, and solar radiation.Event detection focuses on identifying the presence of anevent by detecting or estimating changes the event causesin measurable phenomena like Doppler shift in a radar sig-nal or a change in the acoustic spectral characteristics of theenvironment. Extracting metadata from data requires greatertime complexity than simply collecting the data in the firstplace and it likely requires greater space complexity as well.Data-driven vs Decision-driven Messaging: From aninformation-theory perspective, the amount of communica-tions required to reconstruct a space-time field is a functionof data entropy. That is, the greater the uncertainty or ran-dom variability in the data, the greater the level of commu-nications required to reconstruct it, and the greater the spaceand message complexity. Event detection applications re-quire the system to decide between two or more hypothe-ses by analyzing signals and reporting only when certain hy-potheses are true. Therefore, the message complexity is afunction of event frequency.High-latency Acceptable vs Low-latency Required:Data collection applications can tolerate significant report-ing delays. In contrast, event detection often requires a low-latency between detection and reporting. A consequence oflow-latency is that sensor nodes must listen continuously forradio transmissions or nodes must have the ability to wakeupneighboring nodes quickly. Regardless of how this is im-plemented, an always-on or low-latency wakeup service willconsume more power than either an otherwise equivalenthigh-latency or scheduled service would require.Periodic Traffic vs Bursty Traffic: The message trafficpatterns for data collection and event detection are different.Data collection traffic tends to be periodic and lends itself toscheduled communications. Event detection traffic tends tobe bursty and makes poses different constraints, like latencyand instantaneous throughput,
View Full Document
Unlocking...