/*************************************************************** * * OpenBeacon.org - OnAir protocol position estimator * accepts a text file with tag sightings per reader. * * See the following website for already decoded Sputnik data: * http://people.openpcd.org/meri/openbeacon/sputnik/data/24c3/ * * Copyright 2006 Milosch Meriac * /*************************************************************** /* This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; version 2. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */ /* Input format: ID unix_time reader_id strength(0-3) sequence_counter flags Input file sample: 4042 1198785062 G002 0 0000177200 0 4043 1198785062 H011 2 0000113338 0 4043 1198785062 B007 2 0000113338 0 4043 1198785062 G002 2 0000113338 0 4043 1198785062 F017 2 0000113338 0 4072 1198785062 C012 1 0000201749 0 4252 1198785062 D015 2 0000203074 0 Output file sample: 4067 1198785083 G002 0 0000140380 0 G002:0:017 B007:1:002 Entrance 4100 1198785083 F002 2 0000182746 0 F002:0:010 Angel_Heaven 4041 1198785084 G002 0 0000113647 0 G002:0:013 F017:0:004 Entrance 4068 1198785084 F011 1 0000138513 0 F011:0:008 G021:0:003 Saal_1 4056 1198785084 C015 0 0000406983 0 C015:0:002 Canteen # MOVED Output format explanation: * "4067" is the tag ID * "1198785083" time stamp in Unix time * "G002" the reader which received the current packet * "0" the signal strength (0-weakest, 3-highest) * "0000140380" sequence counter per tag * "0" Flags (2 means that button is pressed) The current list of historical sighting states follows: * "G002:0:017" means that reader G002 has seen the current tag id 17 times since last 30 seconds at the weakest signal strength "0" * "B007:1:002" means that reader B007 has seen the current tag id two times since last 60 seconds at the second weakest signal strength "1" The last column (not including the comment) indicates the currently estimated room. The comment sign '#' indicates annotations to the current tag sighting - usually that the tag actually moved between two rooms. The historical sighting states can be used for triangulation. Make sure to consider the signal strength *and* the amount of packets received at the particular strength. */ #include #include #include #include #include "sort.h" #define DEBUG #define MAX_STRENGTH 3UL #define MAX_FIFO_SIZE 8192 #define MAX_READERS_IN_SIGHT 16 #ifdef DEBUG #define TAG_ERROR(msg) printf("\t%s\n",msg) #elif /*DEBUG*/ #define TAG_ERROR(msg) {} #endif/*DEBUG*/ typedef struct { const char *readers,*name; } TRoomDefinition; TRoomDefinition g_RoomDef[] = { {"D003 D011 D010 E006","Hackcenter"}, {"E013 E017","Lounge"}, {"E013 E017","Lounge"}, {"C007","Hardware_Lab"}, {"D021","Workshop"}, {"F002","Angel_Heaven"}, {"F012","Foebud"}, {"F017","Helpdesk"}, {"G002","Entrance"}, {"B007","Checkroom"}, {"B001","Stairs_Speakers"}, {"E021","Stairs_CERT"}, {"D005 D015","Saal_2"}, {"C005 C023 C150","Saal_3"}, {"C012 C006 D001 C015","Canteen"}, {"G016 G022 F011 G021 A100","Saal_1"}, {"I001","Debian"}, {"I005","Stairs_Press"}, {"I014","Chaoswelle_CAcert"}, {"H011 J013","Wikipedia"}, {"H017","POC_Helpdesk_VOIP"}, {"H019","NOC_Helpdesk"}, {"J019","Stairs_Hinterzimmer"}, // {"C015","Problem_Saal3_Canteen"}, {NULL,NULL} }; typedef struct { unsigned int id,time,strength,sequence,flags,reader,nearest_reader; } TTagSighting; typedef struct { unsigned int id,strength,count; } TBeaconReaderSort; struct TEstimation { struct TEstimation *next,*prev; unsigned int id,sequence,last_seq_change_time,last_time; unsigned int last_reader,last_reader_entry; const char *last_reader_name; int fifo_pos,fifo_count; TTagSighting fifo[MAX_FIFO_SIZE]; int readers_visible; TBeaconReaderSort reader[MAX_READERS_IN_SIGHT]; }; #define TESTIMATION_SIZE (sizeof(struct TEstimation)) #define READER_ID_MASK 0xFFFFUL TTagSighting m_Tag; unsigned int m_BeaconSortTmp[MAX_FIFO_SIZE],m_BeaconLifeTime; struct TEstimation *m_TagFirst=NULL,*m_TagLast=NULL; char m_Reader_Noname[5]; const char* TagGetRoom(unsigned int reader_id) { const char *res; TRoomDefinition *def=g_RoomDef; m_Reader_Noname[0]='A'+(reader_id/1000); sprintf(&m_Reader_Noname[1],"%03u",reader_id%1000); res=NULL; while(def->readers) { res=strstr(def->readers,m_Reader_Noname); if(res) break; def++; } return res ? def->name : m_Reader_Noname; } struct TEstimation* TagFind(unsigned int id) { struct TEstimation *p=m_TagFirst; while(p) if(p->id == id) break; else p=p->next; return p; } void TagEstimatePosition(struct TEstimation* est) { int i,count,j,t; unsigned int *bs,*bss,nid,oid; TTagSighting *p=est->fifo; TBeaconReaderSort *preader; bs=m_BeaconSortTmp; count=0; for(i=0;ififo_count;i++) { if(p->id) { if( ((est->last_time-p->time)*(MAX_STRENGTH+1-p->strength))>(m_BeaconLifeTime*((MAX_STRENGTH+1)/2)) ) p->id=0; else { *bs++=p->reader | (p->strength<<24); count++; } } p++; } if(count>1) { sort(m_BeaconSortTmp,count); bs=bss=m_BeaconSortTmp; oid=*bs++; j=1; t=0; for(i=1;i0xFF) j=0xFF; *bss++=oid|((0xFFL-j)<<16); t++; oid=nid; j=1; } else j++; } count=t; sort(m_BeaconSortTmp,count); } est->readers_visible=0; preader=est->reader; bs=m_BeaconSortTmp; for(i=0;i<(count-1);i++) { nid=*bs++; oid=nid & READER_ID_MASK; if(oid) { bss=bs; for(j=(count-i);j>0;j--) { if(((*bss)&READER_ID_MASK)==oid ) *bss=0; bss++; } preader->id=nid & 0xFFFF; preader->strength=nid >> 24; preader->count=0xFF-((nid >> 16) & 0xFF); preader++; est->readers_visible++; if(est->readers_visible==MAX_READERS_IN_SIGHT) break; } } } int TagProcess(void) { int i; unsigned int u; unsigned char nearest_reader; const char *s; TBeaconReaderSort *preader; struct TEstimation* est; m_Tag.nearest_reader=0; // try to find sighted tag - if not yet seen // add entry to sightings list if((est=TagFind(m_Tag.id))==NULL) { est=(struct TEstimation*)malloc(TESTIMATION_SIZE); if(!est) return 1; est->next=m_TagFirst; est->prev=NULL; est->id=m_Tag.id; est->sequence=m_Tag.sequence; est->fifo_pos=0; est->fifo_count=0; est->last_seq_change_time=m_Tag.time; if(m_TagFirst) m_TagFirst->prev=est; else m_TagLast=est; m_TagFirst=est; } // try to detect replay attacks if(m_Tag.sequencesequence) TAG_ERROR("replay attack detected - wrong sequence:"); else if(m_Tag.sequence==est->sequence) { if((m_Tag.time-est->last_seq_change_time)>=2) TAG_ERROR("replay attack detected - last sequence replayed:"); } else est->last_seq_change_time=m_Tag.time; // store packet to FIFO i=est->fifo_pos; memcpy(&est->fifo[i],&m_Tag,sizeof(m_Tag)); est->last_time=m_Tag.time; est->sequence=m_Tag.sequence; // maintain FIFO counters if(est->fifo_count < MAX_FIFO_SIZE) est->fifo_count++; if(++i == MAX_FIFO_SIZE) i=0; est->fifo_pos=i; TagEstimatePosition(est); preader=est->reader; for(i=0;ireaders_visible;i++) { u=(preader->id/1000); nearest_reader='A'+u; printf(" %c%03u:%u:%03u" ,nearest_reader ,preader->id%1000 ,preader->strength ,preader->count ); preader++; } if(est->readers_visible) { u=est->reader[0].id; s=TagGetRoom(u); printf(" %s",s); i=est->last_reader_name ? est->last_reader_name!=s : est->last_reader!=u; if(i) { est->last_reader=u; est->last_reader_name=(s==m_Reader_Noname)?NULL:s; printf(" # MOVED"); } } putchar('\n'); return 0; } int main(int argc, char *argv[]) { char reader_name[5]; m_BeaconLifeTime=120; while(scanf("%u %u %4s %u %u %u" ,&m_Tag.id ,&m_Tag.time ,&reader_name[0] ,&m_Tag.strength ,&m_Tag.sequence ,&m_Tag.flags )==6) if((reader_name[0]>='A') && (reader_name[0]<='Z')) { m_Tag.reader=1000ul*(reader_name[0]-'A')+atoi(&reader_name[1]); if(m_Tag.reader>READER_ID_MASK) TAG_ERROR("Invalid reader id"); if(m_Tag.strength>MAX_STRENGTH) TAG_ERROR("Invalid strength"); else { printf("%u %u %s %u %010u %u" ,m_Tag.id ,m_Tag.time ,reader_name ,m_Tag.strength ,m_Tag.sequence ,m_Tag.flags ); TagProcess(); } } return 0; }