Protocols for SelfProtocols for Self--OrganisationOrganisationof of a Wireless Networka Wireless NetworkKatayounKatayounSohrabiSohrabi, Jay , Jay GaoGao, , VishalVishalAilawadhiAilawadhiand Gregory J. and Gregory J. PottiePottie, UCLA, UCLADavid Elfersi, EE228IntroductionIntroductionArchitecture and protocols for selfArchitecture and protocols for self--organizing organizing wireless sensor networks:wireless sensor networks:““Wireless ad hoc networks that connect deeply Wireless ad hoc networks that connect deeply embedded sensors, actuators and processorsembedded sensors, actuators and processors””Detects and collects data, processes signals, Detects and collects data, processes signals, transmits its resultstransmits its resultsWireless networking challenges:Wireless networking challenges:••Energy efficientEnergy efficient••Channel accessChannel access••RoutingRoutingGeneral Operational ScenarioGeneral Operational ScenarioOperation under dynamic conditionsOperation under dynamic conditionsStartup, steady state, and failureStartup, steady state, and failureMultihopMultihoproutes to sink nodesroutes to sink nodesLAN established to deal with LAN established to deal with cooperative functionscooperative functionsNew routes are built after the failure New routes are built after the failure of several nodesof several nodesOther Families of NetworksOther Families of NetworksOther types of wireless networks:Other types of wireless networks:••Mobile Ad Hoc Mobile Ad Hoc NETworksNETworks(MANET) greater (MANET) greater mobilitymobility••Cellular Networks operate within clusters Cellular Networks operate within clusters and are connected and are connected througtthrougta wired a wired stationary backbonestationary backbone••Bluetooth is a star network with a master Bluetooth is a star network with a master node node ••HomeRFHomeRFshort distances, singleshort distances, single--hop onlyhop onlyWireless Sensor NetworksWireless Sensor NetworksHundreds to thousands of nodesHundreds to thousands of nodesStationary after deployment except a Stationary after deployment except a very small number of mobile nodesvery small number of mobile nodesTraffic with statistical propertiesTraffic with statistical propertiesLow bandwidth 1Low bandwidth 1--100kb/s100kb/sLong life time, conserve energyLong life time, conserve energy--> Give up on performance> Give up on performanceEnergyEnergy--Conserving Techniques in Conserving Techniques in Sensor NetworksSensor NetworksSensing, data processing, Sensing, data processing, communicationscommunications300 million instructions processed or 300 million instructions processed or 1 1 kbitkbittransmitted over 100 mtransmitted over 100 mEconomy of energy through local Economy of energy through local processingprocessingProtocolsProtocolsSelfSelf--Organizing Medium Access Organizing Medium Access Control for Sensor Networks Control for Sensor Networks (SMACS)(SMACS)EavesdropEavesdrop--AndAnd--RegistrerRegistrer(EAR) (EAR) algorithmalgorithmSequential Assignment Routing Sequential Assignment Routing (SAR) algorithm(SAR) algorithmSingleSingle--Winner Election (SWE) and Winner Election (SWE) and MultiMulti--Winner Election (MWE) Winner Election (MWE)Link Layer IssuesLink Layer IssuesLink Layer services provided to higher Link Layer services provided to higher layers:layers:••Formation of link layer infrastructureFormation of link layer infrastructure••Regulation of channel accessRegulation of channel accessExplicit organization in Explicit organization in time/frequency/code domaintime/frequency/code domain••Discover network connectivity first (neighbors)Discover network connectivity first (neighbors)••Form a hierarchical structureForm a hierarchical structure••Assign collisionAssign collision--free channels accordinglyfree channels accordinglyLink Layer IssuesLink Layer IssuesFirst period for neighbor discoveryFirst period for neighbor discoveryCentralized algorithm: All Centralized algorithm: All connectivity information and connectivity information and bandwidth requirements are passed bandwidth requirements are passed to a single node for calculation of a to a single node for calculation of a schedulescheduleDistributed assignment method: Distributed assignment method: Exchange only with local neighbors Exchange only with local neighborsStationary MAC and Startup Stationary MAC and Startup ProcedureProcedureAssumptions:Assumptions:••Radios can be turned on/offRadios can be turned on/off••Radios are able to tune to different bandsRadios are able to tune to different bands••Number of available bands relatively largeNumber of available bands relatively large••Channel: Pair of time intervals (slots)Channel: Pair of time intervals (slots)••Node deployed randomlyNode deployed randomly••After deployment each node wakes up at After deployment each node wakes up at some random time according to some some random time according to some distribution distributionStationary MAC and Startup Stationary MAC and Startup ProcedureProcedureSMACS: SMACS: ••InfrastructureInfrastructure--building protocol with a flat building protocol with a flat topology (no cluster)topology (no cluster)••Distributed protocol: Allows collection of nodes Distributed protocol: Allows collection of nodes to discover their neighbors and establish to discover their neighbors and establish transmission/reception schedule (no master)transmission/reception schedule (no master)••A channel is assigned to a link immediately A channel is assigned to a link immediately after its discovery after its discovery ••Connected network: There exists at least one Connected network: There exists at least one multihopmultihoppath between any two distinct nodespath between any two distinct nodesStationary MAC and Startup Stationary MAC and Startup ProcedureProcedureCollision avoidance in SMACS:Collision avoidance in SMACS:••Since radio connectivity information is Since radio connectivity information is partial it could result in assigning two partial it could result in assigning two competitive slots to two not yet competitive slots to two not yet discovered neighborsdiscovered neighbors=> To reduce the likeliness of collision => To reduce the likeliness of
View Full Document