AnImproved-SPINProtocolforWirelessSensorNetworks

AnImproved-SPINProtocolforWirelessSensorNetworks

1Shanti, 2k sujatha,3k mahesh

1,2,3( ECE Dept, Sree Dattha Institute of Engineering and Science)

Abstract: InWirelessSensorNetworks(WSN)datatransmissionisonethemajorchallengesandanumberofroutingprotocolshavebeenproposedtocopeupwiththisproblembysavingenergyduringtransmission.Routingprotocolsthatperformsin-networkaggregationarebestsuitedforthispurposetoyieldenergysavingDataTransmission.InthispaperweareproposinganimprovedversionofM-SPINprotocolnamed“I-SPIN”protocol.Ourprotocolaimsatdisseminatingdatatothesinknodethroughshortestpathinsuchawaythattheloadisuniformlydistributedamongallthenodeslyinginthepathandhencetheprobabilityofthenodesofbeingdeadisalmostsame.Thuswedon‟thavetocalculatetheshortestpathasfrequentlyasinM-SPINprotocoland allthesensornodesinthenetworkareutilizedalmostequally.AlsoI-SPINprotocolismorereliablethanM-SPINbecausethedecaytimeofthesensornodesisincreased.

Keywords-WSN,routingprotocols, SPIN

I.INTRODUCTION

Wirelesssensornetworks(WSN)isanetworkconsistofverylargenumberofsensornodeswhicharemuchsmallinsize,lowconstructioncost andhavelimitedmemoryandenergysupply.Butsensornodeshavethecapabilityofsensing,computingandcanperformwirelessdatatransmission.Eachnodeissmallerinsizeandcommunicateswithothernodesinshortrangedistance.

Sensornetworkscanbedeployedforhealthmonitoring,variousindustrialusages,airtrafficmonitoring,underwatersensingandrobotsensingcontrol.Sensortechnologyisoneofthecheapesttechnologiestoprovidesecurityinvery restrictiveenvironments.Thesekindsoftechnologiesaregainingpopularitydaybydayduetobestefficiencyofsecurityandlowcost.Thepracticeofremotesensinghasbecomegreatlysimplifiedbyusefulandaffordablesensorsaswellasrequired software packages. Additionally, users can keepaneyeonthechangingenvironmentconditionsevenfromaremotelocation.

Inordertomonitorchangeseffectivelyinformationmustbetransmittedfromsourcenodetosinknodewithoutlossofdataandinancosteffectiveandenergysavingmanner.So,thesearethevitalconsiderationsinanyroutingprotocol.ThewiderangesofapplicationsthatcanbedeployedontopofWSNmakeitdifficulttodevelopasingleroutingprotocol[1].Thedesignoftheroutingprotocolisstrictlydependentonthenatureoftheapplicationrequirements.Recentresearchesinthisareaalsotargetsonroutingalgorithmsdesignedforachievingbetter performancethatsaves energyofnodesandprovidelongernetworklifetime.

Traditionalroutingprotocolsareaddress-centric.HerepacketsareroutedbasedonuniqueIPaddressesanddatapayloadremainsunchangedduringthe datadeliveryprocess.ButthistypeofaddressingschemeisnotsuitableforWSN,becauseitishardtogloballyidentifythesensornodesinthenetwork.Againduetoenergyandstorageconstraintsofsensornodes,redundantdataareprocessedbeforetheirtransmission.[1]

AsWSNsarequalitativelydifferentfromtraditionalnetwork,theyneeda different routingapproachfortheirdatatoroute.Data-centricroutingisoneofthem.SincemostWSNsareapplicationspecificitisrelativelyadvantageoustoconcentrateondatacontentratherthataddress.Indata-centricroutingscheme,dataareretrievedthroughquerying.Queryingthedataisbasedonsome oftheirattributes values. Inthistype ofroutingprotocol,advertisementorinterestfordataispropagatedthroughoutthenetwork.[1]

II.TRADITIONALSPINPROTOCOL

SPIN(SensorProtocolsforInformation vianegotiation),isafamilyofnegotiation-basedinformationdisseminationprotocolssuitable forwirelesssensornetworks.Thisisastraightforwardprotocolrequiringnoprotocolstateatanynode,anditdisseminates data quickly in a network where bandwidthisnotscarceandlinksarenotloss-prone.ThissectionpresentstheindividualelementsthatmakeuptheSPINfamilyofprotocolsandpresentstwoSPINprotocolsthatwehavedesigned,SPIN-BCandSPIN-EC.[1]

Meta-Data:

Sensorsusemeta-datatosuccinctlyandcompletelydescribethedatathattheycollect.Ifxisthemeta-datadescriptorforsensordataX,thenthesizeof xin bytesmustbeshorterthanthesizeofX,forSPINtobebeneficial.Iftwopiecesofactualdataaredistinguishable,thentheircorresponding meta-datashouldbedistinguishable.Likewise,twopiecesofindistinguishabledatashouldsharethesamemeta-datarepresentation.[1]

SPINdoesnotspecifyaformatformeta-data;thisformatisapplication-specific.SensorsthatcoverdisjointgeographicregionsmaysimplyusetheirownuniqueIDsasmeta-data.Themeta-dataxwouldthenstandfor“allthedatagatheredbysensorx”.A camerasensor,incontrast,mightuse(x,y,fi)asmeta-data,where(x,y)isageographiccoordinateand„fi‟isanorientation.Becauseeachapplication‟smeta-dataformatmaybedifferent,SPINreliesoneachapplicationtointerpretandsynthesizeitsownmeta-data.

SPINMessages:

SPINnodesusethreetypesofmessagestocommunicate:

ADV–newdataadvertisement.WhenaSPINnodehasdatatoshare,itcanadvertisethisfactbytransmittinganADVmessagecontainingmeta-data.

REQ–requestfordata.ASPINnodesendsaREQmessagewhenitwishestoreceivesomeactualdata.

DATA–data message. DATA messages containactualsensordatawithameta-dataheader.BecauseADVandREQmessagescontainonlymetadata,theyaresmaller,andcheapertosendandreceivethantheircorrespondingDATAmessages.[6]

SPINResourceManagement:

SPINapplicationsareresource-awareandresourceadaptive.Theycanpolltheirsystemresourcestofindouthowmuchenergyisavailabletothem.Theycanalsocalculatethecost,intermsofenergy,ofperformingcomputationsandsendingandreceivingdataoverthenetwork.Withthisinformation,SPINnodescanmakeinformeddecisionsaboutusingtheirresourceseffectively.[6]

SPIN-BC:A3-StageHandshakeProtocol

[6]TheSPIN-BCprotocolisasimplehandshakeprotocolfordisseminatingdatathroughalosslessnetwork.Itworksinthreestages(ADV-REQ-DATA),witheachstagecorrespondingtooneofthemessagesdescribedabove.Theprotocolstartswhenanodeobtains newdatathatitiswilling todisseminate.ItdoesthisbysendinganADVmessagetoitsneighbors,namingthenewdata(ADVstage).Uponreceivingan ADV, theneighboring nodechecksto seewhether ithasalreadyreceivedor requestedthe advertiseddata. Ifnot,itrespondsbysendinganREQmessageforthemissingdatabacktothesender(REQstage).TheprotocolcompleteswhentheinitiatoroftheprotocolrespondstotheREQwithaDATAmessage,containingthemissingdata(DATAstage).

Figure1showsanexampleoftheprotocol.UponreceivinganADVpacketfromnodeA,nodeBcheckstoseewhetheritpossessesalloftheadvertiseddata(a).Ifnot,nodeBsendsanREQmessagebacktoA,listingallofthedatathatit wouldliketoacquire.

Figure3:TheSPIN-BCProtocol.NodeAstartsbyadvertisingitsdatatonodeB(a).NodeBrespondsbysendingarequesttonodeA(b).Afterreceivingtherequesteddata(c),nodeBthensendsoutadvertisementstoitsneighbors(d),whointurnsendrequestsbacktoB(e,f).

(b).WhennodeAreceivestheREQpacket,itretrievestherequesteddataandsendsitbacktonodeBasaDATAmessage(c).NodeB,inturn,sendsADVmessagesadvertisingthenewdataitreceivedfromnodeAtoallofitsneighbors(d).ItdoesnotsendanadvertisementbacktonodeA,becauseitknowsthatnodeAalreadyhasthedata.Thesenodesthensendadvertisementsofthenewdatatoalloftheirneighbors,andtheprotocolcontinues.

Thereareseveralimportantthingstonoteaboutthisexample.First,ifnodeBhaditsowndata,itcouldaggregatethiswiththedataofnodeAandsendadvertisementsoftheaggregateddatatoallofitsneighbors(d).Second,nodesarenotrequiredtorespondtoeverymessageintheprotocol.Inthisexample,oneneighbordoesnotsendanREQpacketbacktonodeB (e).Thiswouldoccurifthatnodealreadypossessedthedatabeingadvertised.

Thoughthisprotocolhasbeendesignedforlosslessnetworks,itcaneasilybeadaptedtoworkinlossyormobilenetworks. Here, nodes couldcompensateforlostADVmessagesbyre-advertisingthesemessagesperiodically.NodescancompensateforlostREQandDATAmessages byre-requestingdata itemsthat do notarrivewithinafixedtimeperiod.Formobilenetworks,changesinthelocaltopologycantriggerupdatestoanode‟sneighborlist.Ifanodenoticesthatitsneighborlisthaschanged,itcanspontaneouslyre-advertiseallofitsdata.

Thisprotocol‟sstrengthisitssimplicity.Eachnodeinthenetworkperformslittledecisionmakingwhenitreceivesnewdata,andthereforewasteslittleenergyincomputation.Furthermore,eachnodeonlyneedstoknowaboutitssingle-hopnetworkneighbors.Thefactthatnoothertopologyinformationisrequiredtorunthealgorithmhassomeimportantconsequences.First,SPIN-BCcanberuninacompletelyunconfigurednetworkwithasmall,startupcosttodeterminenearestneighbors.Second,ifthetopologyofthenetworkchangesfrequently,thesechangesonlyhavetotravelonehopbeforethenodescancontinuerunningthealgorithm.

SPIN-EC,SPIN-BCwithaLow-EnergyThreshold

TheSPIN-ECprotocoladdsasimpleenergy-conservationheuristictotheSPIN-BCprotocol.Whenenergyisplentiful,SPIN-ECnodescommunicateusingthesame3-stageprotocolasSPIN-BCnodes.WhenaSPIN-EC node observesthatitsenergyisapproachingalow-energy threshold, itadaptsby reducing itsparticipationintheprotocol.Ingeneral,anodewillonlyparticipateinastageoftheprotocolifitbelievesthatitcancompletealltheotherstages oftheprotocol withoutgoing belowthelow-energy threshold.Thisconservativeapproachimpliesthat,ifanodereceivessomenewdata,itonlyinitiatesthethree-stageprotocolifitbelievesithasenoughenergytoparticipateinthefullprotocolwithallofitsneighbors.Similarly,ifanodereceivesanadvertisement,itdoesnotsendoutarequestifitdoes nothave enoughenergytotransmittherequest and receive the corresponding data. Thisapproachdoesnotpreventanodefromreceiving,andthereforeexpendingenergyon,ADVorREQmessagesbelow its low-energy threshold. It does, however,preventthenodefromeverhandlingaDATAmessagebelowthisthreshold.[1]

III.MODIFIEDSPINPROTOCOL(M-SPIN)

Infewapplications suchasalarmmonitoringapplicationsneedquickandreliableresponses.Supposeinforestfirewarningsystem,quickresponseisneededbeforeanydisasteroccurs.Inthiscase,itisdesirable

thatdatamustbedisseminatedtowardsthesinknodeveryquickly.[1]

Figure2.DataTransmissioninaWirelessSensorNetwork

M-SPINroutingprotocolisbetterapproachforsuchtypeofapplicationsthanSPIN.InM-SPIN,weaddanewphasecalledDistancediscoverytofinddistanceofeachsensornodeinthenetworkfromthesinknodeintermsofhops.Thismeansthatnodeshavinghighervalueofhopdistancearefarawayfromthesinknode.OtherphasesofM-SPINareNegotiationandDatatransmission.Onthebasisofhopdistance,Negotiationisdonefor sendinganactualdata.Therefore, useof hopvaluecontrolsdisseminationofdatainthenetwork.Finally,dataistransmittedtothesinknode.Herethemainadvantagewas thatdataistransmittedtoonlythosenodesthatareresidinginthepathendingatthesinknode.Thus,preventstheextraburdontotransmitdatatoallthasensornodesandsavingasignificantamountofenergy.[1]

Figure3.DistanceDiscoveryPhase

Figure2 showstheDistancediscovery phaseofM-SPIN.Hopdistanceismeasuredfromsinknodes.InitiallythesinknodebroadcastsStartuppacketinthenetworkwithtype,nodeIdandhop.Heretypemeanstypeofmessages.ThenodeIdrepresentsidofthesendingnodeandhoprepresentshopdistancefromthesinknode.Initialvalueofhopissetto1.WhenasensornodereceivestheStartuppacket,it storesthishopvalueasitshopdistancefrom thesinknodeinmemory.Afterstoringthevalue,thesensornodeincreasesthe hopvalueby1andthenre-broadcasttheStartuppackettoitsneighbournodeswithmodifiedhopvalue.ItmayalsobepossibleforasensornodetoreceivemultipleStartup packets from different intermediate nodes

WheneverasensornodebreceivesStartup packetsfromitsneighborsai, 1≤ i ≤n,itchecksthehopdistancesandsetthedistancetotheminimum,i.e.

h(a b) in}imin∀,, =1,

Whereh(ab)i,representshopdistancesbetweenthenodesaiandbandnistheno.ofneighbornodesofnodebfromwhichitreceivesthestartuppackets.

TheNegotiationphaseisalmost similar to the SPIN-BCprotocol. The source node sends an ADV message.UponreceivinganADVmessage,eachneighbournodeverifieswhetherithasalreadyreceivedorrequestedtheadvertised data. Not only that, receiver node alsoverifieswhetheritisnearertothesinknodeornotincomparison with the node that has sent the ADVmessage. This is the main difference between thenegotiationphaseofSPIN_BCandthatofM-SPIN.Ifhopdistanceofthereceivingnode(own_hop)islessthanthehopdistancereceivedbyitaspartoftheADVmessage(rcev_hop),i.e.own_hoprcev_hop,thenthereceivingnodessendREQmessagetothesendingnodeforcurrentdata.ThesendingnodethensendstheactualdatatotherequestingnodeusingDATAmessage.[1]The Data transmission phase is same as SPIN-BCprotocol.Afterrequestisreceivedbythesourcenode,dataisimmediatelysenttotherequestingnode.

Figure4.TheM-SPINprotocol.(1)Node1startsadvertisingitsdatatoallofitsneighbors.(2)Node3respondsbysendingarequesttonode1.(3)Afterreceivingtherequest,node1sendsthedata.(4)Node3againsendsadvertisementouttoitsneighborsforthedatathatitreceivedfromnode1.

  1. PROPOSEDWORK

Improved-SPINProtocol(I-SPIN)

OurprotocolI-SPINundertakesalltheadvantagesofM-SPINprotocolButremovesthemajordisadvantage.InourproposedprotocolalsotheNegotiationphaseanddatatransmissionphasewillbesameasinM-SPINprotocolbutwehavemodifiedtheDistanceDiscoveryphasetoremovethedemerits.

AsinmodifiedSPIN (M-SPIN),here alsonegotiationisdonebeforesendingtheactualdata.Butinourscheme,onlythenodeswhichlieinashortestpathtosinknodesendREQpacketsinresponsetoADVpacketfromthesourcenode.Thereforedataisdisseminatedtothesinkorneighbournodestowardsthesinknode.I-SPINachievesenergysavingsbydiscardingpackettransmissiontotheoppositedirectionofsinknode.

TheproblemofM-spinprotocolisthatfewsensornodesmaybeusedseveraltimesandmaybedestroyedearlierthanothernodesinthenetworkandwehavetocalculatetheshortestpatheverytimea sensornodedestroyedinthenetwork.Thusnodatatransmissionwillbedoneuntilwecalculatethenextshortestpath.InI-SPINprotocolwecalculateshortestpathfromsinknodetoallothernodesinthenetworkonlyonetimeatthebeginningoftheprotocol.

InI-SPINprotocolweareusingtheBellman-FordAlgorithmtocalculatetheshortestpaththroughwhichdataistransmittedtothesinknode.

DistanceDiscoveryPhase:

Workingofthisphaseisexplainedbyfollowingfigure:

A.Figure:5DistanceDiscoveryPhaseofI-SPINProtocol

Requirement:

Excepttheneighboursofsinknodeseachnodeinthenetwork will contain three variables hp-val(shortest distancefromsink),hp-id(idofnodecomingfirstinshortestpath),counter(initially1)andatablenamedSAR(havingmax2columns).

Steps:

StepsoftheDistancediscoveryphaseisasfollows:

  • InitiallythesinknodebroadcastsStartuppacketinthenetworkwithtype,node-Idandhop.Heretypemeanstypeofmessages.Thenode-Idrepresentsidofthesendingnodeandhoprepresentshopdistancefromthesinknode.Initialvalueofhopissetto1.[1]
  • WhenasensornodereceivestheStartuppacket,itstores thishopvalueinhp-valandnode-idinhp-id.Afterstoringthevalue,thesensornodeincrementsthehopvalueby1andthenre-broadcasttheStartuppackettoits neighbournodes with modifiedhop value. Itmayalso be possible for asensor nodetoreceivemultipleStartuppacketsfromdifferentintermediatenodes..WheneverasensornodebreceivesStartuppacketsfromitsneighbouraitcomparesthehopvaluewithhp-valandsetthehp-valtotheminimumandupdatehp-idaswell.

a)Ifhp-val=hop-value,nodebaddshp-valasfirstcolumn headof tableSARandwritehp-valas firstrow,thensecondrowandsoonifsameisrepeatedagain.

b)Ifhp-val+1=hop-value , nodebaddshp-val assecond column head oftableSAR andwritehp-valasfirstrow,thensecondrowandsoonifsameisrepeatedagain.

AftertheendofDistanceDiscoveryphase,Allnodesinthenetworkhavetheshortestpathlengthtosinknode.Thevaluesofhp-valand hp-id ofallnodesisshowninfigure-4itselfwhereasthetablesofallnodesaccordingtofigure-4,areasfollows:

a)ifthevalue=1,thennode-hwilltransmitthepackettonodehavinghp-idasitsnodeidi.enode-einthiscaseandthenincrementcounter.

b)ifthevalue=2,thennode-hwillcheckitsSARtableforcolumnhavinghead=hp-valandhead=hp-val+1. ifonlyhp-valcolumnispresentthenitwillrandomlyselectoneofthenode-idfromanyrowandtransmitdatatoit.Thendecrementthecounter.

elseifcolumnwithhead=hp-valisnotpresentbutcolumnwithhead=hp-val+1ispresentthenitwillrandomlyselectoneofthenode-idfromanyrowofitandtransmitdatatoit.Thendecrementthecounter.

else ifnocolumn is therethenitwillforwardthepackettonodehavinghp-idasitsnodeidanddecrementthecounter.

elseifbotharepresentthenitwillrandomlyselectoneofthenode-idfrom anyrowofhp-valcolumnandtransmitdatatoit.Thenincrementthecounter.

c)ifthevalue=3(i.ebothcolumnsarepresent)thenitwillrandomlyselectoneofthenode-idfromanyrowofhp-val+1columnandtransmitdatatoit.Thensetcounter=1.

Anyoftheintermediatenodewillfollowthestepsabcuntildataisreceivedbysinknode.Datatransmissiontoanynodeisdonethroughnegotiation.

FailureresistantI-SPIN:

Ifanyofthenodefails:

a)before sending actualdata anode-h willsendADVmsgtotargetnodeonly.onrecevingADVmsgtargetnode willsendREQmsgtonode-h.

Ifnode–hwillreceivetheREQmsgthenonlyitwilltransmitactualdata

Otherwisenode-hwillremovethatnode-idandfollowanyofthestepsa,borcwhicheverisapplicable.Datatransmissionwillnotstopevenafterfailureofanynode

Advantage:

  • Aswearerandomlyselectingintermediatenodes,Nonodewillgetextraburdononitandtheprobabilityofgettingdecayedwillbedividedalmostequallyamongallthenodes.
  • Duetorandomselectionshortestpathwillalsochangeforsamenodeifitistransmittingagainthesecondtime,soabovepointwillbeforallnodesinnetwork.
  • WehavetocalculatetheshortestpathonlyonetimeduringthestartingoftheProtocol.
  • TransmissionwillnotbestoppedduetodecayofanynodeasitwillbesimplyeliminatedfromthePATH.
  • LifetimeofWSNwillincrease.

REFERENCE

[1]ZeenatRehena, Sarbani Roy , NandiniMukherjee:AModifiedSPINforWirelessSensor Networks , 978-1-4244-8953-4/11/©2011IEEE

[2]K.Akkaya,M.Younis:ASurveyonRoutingProtocolsforWirelessSensorNetworks.In:ElsevierAdHocNetworkJournal,Vol.3,pp.325-349,2005.

[3]I.F.Akyildiz,M.C.Vuran,O.Akan,W.Su:WirelessSensorNetworks:ASurveyRevisited.In:ComputerNetworksJournal(ElsevierScience),Vol.45,no.3,2004.

[4]J.Kulik,W.R.Heinzelman,H.Balakrishnan:Negotiation–BasedProtocolsforDisseminatingInformation inWirelessSensor Networks, Vol8,pp.169-185,2002.

[5]F.Zabin,S.Misra,I.Woungang, H.F.Rashvand,

[6]N.W.Ma, M.A.Ali:REEP: data-centric, energy-efficientandreliableroutingprotocolforwirelesssensornetworks.In:IETCommun.Vol.2,No.8,pp.995-1008,2008

[7][6] Adaptive Protocols for InformationDisseminationin WirelessSensor NetworksJoannaKulik,WendiRabiner,andHariBalakrishnan,1999

Page | 1