Abstract-Vi undersöker ett unikt schemaläggningsproblem i trådlösa sensornätverk där alla noder i ett kluster skickar exakt ett paket till en utsedd diskbänk nod med målet att minimera överföringstiden. Svårigheten ligger i att nodöverföringar måste vara tillräckligt isolerade antingen i tid eller i rymden för att undvika kollisioner. Problemet är formulerat och löst via graf representation. Vi bevisar att med specifika nätverk topologier (antingen linje eller träd), kan ett optimalt överföringsschema uppnås effektivt genom ett pipeline-liknande schema. Den minsta tid som krävs för en linje (eller träd) topologi med n noder är 3 n - 2). Vi bevisar vidare att vårt schemaläggningsproblem är NP-hårdt för allmänna grafer. Vi föreslår en heuristisk algoritm för allmänna grafer. Vår heurist försöker schemalägga så många oberoende segment som möjligt för att öka graden av parallell överföring. Denna algoritm jämförs med en RTS/CTS-baserad distribuerad algoritm. Preliminära simulerade resultat indikerar att vår heuristiska algoritm överträffar RTS/CTS-baserad distribuerad algoritm (upp till 30%) och uppvisar ett stabilt schemaläggningsbeteende. Index Terms-Sensor nätverk, hybrid nätverk, schemaläggning, allt-ett informationsinsamling I. INLEDNING Framsteg inom trådlöst nätverk och önskan om insamling av data i realtid har resulterat i en enorm ökning av forskningsverksamheten inom området trådlösa sensornätverk. En viktig tekniktrend är utvecklingen av storskaliga heterogena nätverksarkitekturer som är integrerade med olika kommunikationstekniker för bättre prestanda. I sådana nätverksarkitekturer är billiga batteridrivna sensornoder vanligtvis utrustade med (flera) datasensorkomponenter, begränsade databehandlingskomponenter och kortdistanskommunikationskomponenter. Den grundläggande datainsamling funktionaliteten tillhandahålls genom paket återutläggning bland sensornoder, där data så småningom tas emot på en central plats. Denna metod är dock inte skalbar och kan inte hantera aggregerad trafik när hundratals eller tusentals sensornoder används. För att stödja storskaliga sensornätverk och snabb insamling av tidskritiska data är nätverket ofta organiserat i kluster [2] där information först samlas in vid klusterhuvudet och sedan ytterligare samlas in av mobila basstationer såsom obemannade fordon. En viktig länk till ett sådant nätverk paradigm är effektiv paket routing inuti kluster. Mycket forskning har utförts på routing i sensornätverk baserat på ad hoc-karaktär sensornätverk [4], [5], [1], [3] vilket resulterar i distribuerade routing algoritmer. Dessa distribuerade algoritmer är i sig konkurrensbaserade, såsom i [5] och [7]. Därför är deras prestanda starkt beroende av densiteten hos sensornoder och trafikmönster.
Choi et al REF visade att konvergerande schemaläggningsproblem är NP-hårda i svag bemärkelse.
Scheduling on sensor hybrid network
{'venue': 'Proceedings. 14th International Conference on Computer Communications and Networks, 2005. ICCCN 2005.', 'journal': 'Proceedings. 14th International Conference on Computer Communications and Networks, 2005. ICCCN 2005.', 'mag_field_of_study': ['Computer Science']}