INFOCOM 2003Return to Main MenuRobust Location Detection inEmergency Sensor NetworksSaikat Ray, Rachanee Ungrangsi, Francesco De Pellegrini,Ari Trachtenberg, David StarobinskiAbstract— We propose a new framework for providing robustlocation detection in emergency response systems, based on thetheory of identifying codes. The key idea of this approach is toallow sensor coverage areas to overlap in such a way that eachresolvable position is covered by a unique set of sensors. In thissetting, determining a sensor-placement with a minimum numberof sensors is equivalent to constructing an optimal identifyingcode, an NP-complete problem in general. We thus proposeand analyze a new polynomial-time algorithm for generatingirreducible codes for arbitrary topologies. We also generalize theconcept of identifying codes to incorporate robustness propertiesthat are critically needed in emergency networks and providea polynomial-time algorithm to compute irreducible robustidentifying codes. Through analysis and simulation, we showthat our approach typically requires significantly fewer sensorsthan existing proximity-based schemes. Alternatively, for a fixednumber of sensors, our scheme can provide robustness in theface of sensor failures or physical damage to the system.I. INTRODUCTIONCommunication systems play an essential role in emergencysituations such as fires, building collapses or extreme weatherphenomena. Unfortunately, existing systems often provideminimal communication infrastructure for supplying informa-tion about the nature or the extent of a disaster in situ.Asa result, first responders typically enter emergency situationswith little real-time information about the site, and, shouldthey become trapped, only a haphazard means of rescue areavailable to them. One promising method for providing real-time feedback from disaster sites involves the use of sensornetworks.Recent advances in sensor technologies [1–3] make it pos-sible to install and interconnect tiny devices within existinginfrastructure, such as smoke detectors or overhead lighting,for networked use in case of an emergency. These networkscould provide emergency control centers with 3D buildingvisualization, real-time monitoring of hot spots or structurefailures, and tracking of victims and personnel.Central to such features is the ability to perform indoor lo-cation detection in the face of unpredictable reflections (fromfurniture, people, walls), occlusions (due to smoke, fire), andchanging building topology (from falling walls, collapsed ceil-ings). Indeed, many essential tasks of an advance emergencyresponse system require the following capabilities:The authors are with the Electrical and Computer Engineering Departmentat Boston University. This work was partially supported by the NationalScience Foundation under NSF Career Grant CCR-0133521, NSF CAREERgrant ANI-0132802 and by a SPRInG award from Boston University.• To enable crew members to identify their own and others’locations.• To locate victims, potential hazards, or sources of theemergency.• To identify and rescue trapped personnel.Though several indoor location detection schemes have beendescribed in the literature (see Section II), none of themhave been designed for the specific working conditions ofemergency networks, and are thus generally unsuitable forthis purpose. Chiefly, they lack robustness against equipmentfailures and changing structural topology. In particular, severalexisting systems are proximity-based, in which user locationis determined by nearby sensors (also called beacons). Whensensors fail in such systems, an entire coverage area is lost.In this paper, we propose to address the issue of robustlocation detection through a novel framework based on thetheory of identifying codes [4]. Our approach generalizes exist-ing proximity-based location detection techniques by allowingsensor coverage areas to overlap. Our key idea is to ensure thateach resolvable position be covered by a unique set of sensors,which then serves as its signature.In general, our approach exhibits two major advantages overexisting location detection schemes:1) For a fixed number of sensors, each with a given cover-age area, our scheme can perform location detection ata finer resolution than a scheme which does not allowoverlapping coverage areas.2) Our solution can be designed to function correctly evenin the face of corruptions or failures in the system.These two advantages trade off with one another, meaning that,given a fixed number of sensors, one can design a systemwith finer resolution at the expense of robustness, or morerobustness at the expense of resolution.The main challenge in designing our system is to positionsensors so that every resolvable location can be identifiedunambiguously. Moreover, despite the projected decreasingcost of sensors, it is desirable to minimize the number of activesensors at a time (i.e., not in sleep mode), thus extending thelifetime of the network. Thus, our goal is to perform locationdetection, at a given level of robustness, using a minimumnumber of sensors. For this purpose, we resort to the theoryof identifying codes, which provide a general technique foruniquely identifying nodes in a graph.At a high level, we model a location detection system as agraph by dividing a continuous coverage area into a finite set0-7803-7753-2/03/$17.00 (C) 2003 IEEE IEEE INFOCOM 2003of regions. Each region is represented by a single point withinits boundary. These points correspond to nodes in a graph andnodes are connected by links in the graph if the correspondingpoints in the physical system are able to communicate directly.The identifying code problem is then to determine the nodeson which to place the codewords such that each node of thegraph is covered by a unique set of sensors; the locationdetection analog of this would be to designate special sensornodes in such a way that every node in the graph is withincommunication range of a unique set of sensors.The problem of finding an optimal identifying code foran arbitrary graph is NP-complete [5]. Instead, we proposea novel greedy algorithm, called ID-CODE, that produces ir-reducible identifying codes. An identifying code is irreducibleif no codeword can be removed while still keeping everyposition uniquely identifiable. Our numerical results show thatthe solution produced by our algorithm is close to the optimalsolution, for a wide range of parameters.Furthermore, we introduce the