accounttoutoulu.com

FREQUENCYHOPPINGMOBILEADHOCANDSENSORNETWORKSYNCHRONIZATIONTeemuVanninen,MattiRaustia,HarriSaarnisaariandJariIinattiCentreforWirelessCommunications/UniversityofOulu,Finlandteemu.
vanninen@ee.
oulu.
ABSTRACTThetimesynchronizationisoneofthemainissuesinfre-quencyhoppingmobileadhocnetworks(FHMANET)ortimesynchronouswirelesssensornetworks(TWSN).
IntheformercaseanetworkwidetimereferenceisneededinFHcodephasesynchronizationandinthelattercase,e.
g.
,intimestampingofthesensedphenomenon.
Herein,adis-tributeddecisionmakingmethod(s)thatsolvestheproblemsconsideringinitialtimesynchronization,FHcodephasesynchronization,late-entrynodesandsubnetworkmergingcasesoftacticalFHMANETsandTWSNsisproposed.
Oneofthestartingpointsisarecentlydevelopedrobustcontrolchannelmethodthatenablesthenodestoexchangethenec-essarysynchronizationmessagespriorthefrequencyhop-pingsynchronism,i.
e.
,out-of-phase.
Theproposedmethodismasterfreeandbasedonnodeidentiersandlocalinfor-mationthatanodecollectsfromthesurroundings,namelylocaldensityandlocaldata-activity.
Simulationresultsaregiventhatprovethefunctionalityandthepotentialityoftheproposedmethods.
I.
INTRODUCTIONArealtimeandcomprehensivesituationalpictureismoreorlessdefaultexpectationinmoderncrisismanagementandOperations-Other-Than-War(OOTW).
Forthis,moreandmoredemandsareimposedtothesensoranddatanetworksinordertoaccomplishthehighdemands.
Forexampleanti-jamming(AJ),lowprobabilityofdetectionandinterception(LPD/LPI)andhighmobilityareusuallyrequired.
ThewellknownsolutiontoenablemobilityhasbeenMANET(MobileAdHocNetwork).
Theinfrastructurelessconstruc-tionofaMANETtendsalsotorobustfythenetworkssinceMANETsdonothavesingleweakspotsasallthenodesactsassources,sinksandrouters.
Ontheotherhand,thecom-plexityoftheindividualnodes,andthus,thewholenetworkisincreasedconsidering,e.
g.
,routing,channelaccessandsynchronization.
RoutingandMAC(MediumAccessCon-trol)protocolshavebeenwidelyinvestigatedinrecentyears[1,2].
Thesynchronization,however,hasnotgainedasmuchat-tention,sincethesynchronizationinanadhocnetworkdoesnotbasicallydifferfromsynchronizationinacentralizedcontrolnetwork,wherebothtimeandfrequencydomainshavetobeconsideredbythelinkbasis.
Unfortunatelythisisvalidonlywhenexcludingthenetworkwidetimesyn-chronizationandfrequencyhopping,sincethecomplexityisincreased,e.
g.
,duetouncertaintyoftheusedhopfrequency(FH-codephase)foranodebeforeitssynchronization.
IfFHisusedtoincreaseLPI,LPD&AJpropertiesinsteadofmul-tipleaccess,thetaskistosynchronizetheFH-codephasetobethesameforeverynodeinthenetwork.
Thisintroducesanambiguityproblem:whowilldecidetheusedFH-codephaseandtimereferenceandhowallthenodeswillenduptothesamedecisionWhenFHisutilizedinaMANETthereshouldbepossi-bilitytoaccomplishlate-entriestothenetworkforindivid-ualnodes.
Inaddition,thereshouldbealsopossibilityfornetworkmergingwhentwo(ormore)separatelyinitializednetworksmovetotheRF(RadioFrequency)rangeofeachother.
Furthermore,re-merging,i.
e.
,commonlyinitialized,ofnetworkpartitionsshouldbeenabled.
Similarambiguitychallengesareencounteredwithmerenetworktimingsyn-chronization,andaccordingly,samekindofsynchronizationmethodscouldpresumablybeusedinbothFHMANETsandtimesynchronouswirelesssensornetworks(TWSN).
TobeafullyMANETandTWSNcompatiblesynchroniza-tionmethod,thenetworksplitting,re-mergingormergingshouldcausenodistortionoronlyminimaldistortiontothesynchronism.
Afterthenetworktimingand/orFHcodephaseinitializa-tion,thenetworktimesynchronizationisneededbecausethefrequencyreferenceshaveatendenciestodriftcom-paredtotheirnominalfrequency.
Adiscretenetworktimesynchronizationalgorithmin[3]solvestheclocknetun-ingproblem,i.
e.
,synchronizationmaintainingprobleminaFHMANETbut,however,lacksaspiltting-mergingandlate-entryrelateddecisionmakingfunctionalities.
Dis-tributeddecisionmakingcanexploit,e.
g.
,nodeIDs(Identi-er)[4,5].
However,theshortcomingsofamereIDbaseddecisionmakingwasacknowledgedin[6]tobewithlate-entrynodesandnetworkmerging.
Therelevantnetworktopologycontrolhasbeenissuedinnumerouspapers[7,8,9,10]andanetworkdivisiondetec-978-1-4244-2677-5/08/$25.
002008IEEE1of7tionmethodin[11].
Themethodin[10]exploitstheGPS(GlobalPositioningSystem),whichcouldbefairlyeasilydisabledbyjammingtheweakGPSsignals[12].
Thesyn-chronizationmethodin[13]exploitsaxedfrequencydo-maincontrolchannelwhomeverynodeissupposedtolistenonaregularbasis.
Itisdeclaredthatthemethodenablesboththelateentriesandsubnetworkmergingbut,however,thenecessarydistributeddecisionmakingisnotconsidered.
Allofthemethodsreferencedhereinfailtosolvetheprob-lemsrelatedtosustainingacommontimereference/FHcodephasewhenlate-entriesandnetworksplitting/merg-ingoccur.
Thespecialcasesofthelateentrynodesandnetworkre-mergingandmergingcasesareaddressedinthispaper.
Adistributeddecisionmakingmethodsarepresentedtosolvetheknownissuesconsideringtheseunsolved(asfarastheauthorsknow)problems.
II.
BACKGROUNDReference[4]proposestoplacethecontrolchannelincodedomainaccordingtotheDS-CDMA(DirectSequenceCodeDivisionMultipleAccess)principle.
Consequently,boththesynchronizationdataandthepayloaddataaremultiplexedinthetransmitterandsimultaneouslytransmittedthroughthechannel.
Bothofthesedatasarespreadwithindivid-ualnearorthogonalDSspreadingcodes.
Ifnegligiblemulti-pathpropagationisassumedthesedatacomponentscanbedemodulatedfromthesumsignalvirtuallywithoutinterfer-encetoeachother.
Boththenodesbelongingtothenetworkandthenodestry-ingtojoinitaresupposedtoknowalltheusedDScodes(ifapplicable),theusedhopchannels,thehoppingrateandtheusedhoppingcode.
FHisusedforimprovedrobustness,notformultipleaccessmethodortoimprovethenetworkcapac-itybyexploitingachannelizingmethod.
Thesynchroniza-tiongoalistoachievethenetworkwidecommonhoppingphase,andthus,theunknownfactoristhecommonnetworktime.
Herein,anetworkischaracterizedbyanetworkID(NID)thatisidenticalwiththenodeIDofthetimingorigi-natoraspresentedin[4].
IfthesystemisahybridSFH/DSSS(SlowFH,DSSpreadSpectrum)itsthoroughsynchronizationhastobeconductedinmultiplephasesthroughan(out-of-phasefunctioning)controlchannel[4].
First,theDScodephasehastobesolvedandafterthattheFHtiming,i.
e.
,thetimeinstantwhentochangethefrequency(takingaccountthepropa-gationdelay).
BoththeDScodephaseandtheFHtimingcanbeeffectivelyestimatedthroughmatchedlteringasde-scribedin[4].
Afterthesephasesthereceiverhasacapabil-itytochangefrequencysynchronously,i.
e.
,hopattherighttimeinstantandtosampleattherighttimeinstancesthein-comingsignal.
However,itdoesnothaveknowledgeaboutthecurrentFHcodephase,i.
e.
,localtimereferenceofthetransmitter.
Forthis,thetransmitter-receiverpairhastobeabletoexchangetimereferenceinformation,i.
e.
,transfersynchronizationmessages.
Furthermore,thesynchroniza-tionmessageshavetobetransmittedperiodicallyaspre-sentedin[4].
Theassumptionsgivenaboveareconsideredtobefairforanodethathasbeengrantedanopportunitytojointthenet-work.
Furthermore,itisassumedthatGNSS(GlobalNavi-gationSatelliteSystem)timingisnotavailablewhichcouldbeveryeffectivelyusedfornetworktimesynchronization.
III.
PROPOSEDMETHODThischapterpresentsanoveldistributeddecisionmakingmethodforFHMANETsandTWSNsthatenableslateen-triesandbothnetworkre-mergingandmerging.
Atrst,itisdiscussedaboutthestartingpointsandpositionedthegoalsforthemethod.
A.
DesignprinciplesandthegoalsReference[14]discussesaboutselforganizationininforma-tionnetworksandpresentsfourprinciplestobeusedwhendesigningselforganizingfunctionalitiesforanetwork:Rule1"DesignLocalBehaviorRulesThatAchieveGlobalProp-erties";Rule2"DoNotAimForPerfectCoordination:Ex-ploitImplicitCoordination";Rule3"MinimizeLong-LivedStateInformation";Rule4"DesignProtocolsThatAdaptToChanges".
Forexamplein[15]theabovementionedde-signprinciplesareusedtocompriseanetworkclustercon-trolingmethod.
Inthispapertheseprinciplesaretakenintoaccountbut,however,areseenratherasaframeworkthanrules.
Herein,thegoalsforthemethodarepositionedsothattheforeseenusecasesofaMANETarefullled:Goal1"Ini-tialsynchronization"ThemethodhastoofferameantoconductaninitialsynchronizationforanFHMANEToraTWSN.
Thismeansanintervalfromthestartuptoastatewhereacommontimingand/orFHcodephaseisachievedwithinthenetwork.
Forthis,e.
g.
,distributeddecisionsaboutthetimingoriginatorhastobedone.
Goal2"Re-mergingofnetworkpartitions"Theanticipatedcasewhereanex-2of7istingnetworksplitstotwosubnetworksisproblematicbe-causeinthatcaseboththesubnetworkshavethesameNIDs1.
Therefore,whenthepartitionsarere-mergingtheoc-currencecannotbeidentiedjustbycomparingtheNIDs.
Consequently,afterthere-mergingincidentboththesubnet-workstrytonetunetheirdivergenttimereferencesbyatimesynchronizationalgorithm,althoughitwouldbefavor-abletore-initializethetimereferenceofeitherofthesub-networks.
Especially,whentheinstanterrorsbetweenthesubnetworktimereferencesishighitwouldtakeconsider-ablylongertimetonetunethetimereferencebythesyn-chronizationalgorithmthantore-initialize,i.
e.
,changethereference[3].
Therefore,amethodforidentifyingthere-mergingcasetogetherwithadistributedmethodonhowtochoosethetimingoriginatorinare-mergednetworkhastobedeveloped.
Goal3"Mergingofnetworks"Separatelyini-tiatednetworkshavedifferentNIDsandtimereferences,andthus,theoccurrenceofnetworkmergingcanbeidentiedbycomparingtheNIDs.
Therefore,adistributedmethodonhowtochoosethetimingoriginatorinmergingnetworkshastobedeveloped.
B.
InitialSynchronizationWhentheinitialsynchronizationisbasedonthesimplenodeIDcomparisonthenodeswithIDsmallerthanlargestIDex-periencemultiplere-initializationsoftheirtimereferencesbeforeacommontimingisachieved.
Thatisbecauseinhomogenousnetworkeverynodehasasameprobabilitytostartthesynchronizationmessagebroadcastingatarandomtimeinstantintheinitializationphase[4].
Thetimerefer-enceischangedeverytimeanodereceivesamessageorig-inatedbyanodewithahigherIDthanitsown.
Therefore,intheworstcasetheamountoftimingchanges,Sv,canbecalculatedasSv≤NN1,(1)whereNNisthenumberofnodeswithinthenetwork.
Duetotimingchangesthereareinitiallymultiplenetworkclus-terswiththeirowntimereferences,andasaconsequence,thedatatransferbetweentheseclustersisnotpossible(whenanFHwaveformisconsidered).
Eventhougheventuallyallthenodesconvergetothesametimingitispossibletoen-hancetheratetheyconverge,e.
g.
,bytakingadvantageoftheneighborinformation.
Forexample,uponreceivingalargerIDsynchronizationmessagethereceivernodecouldpromptlyinformitsinstantneighborsabouttheoccurrence1Notethatthecaseisanalogousalsowithmorethantwore-mergingsubnetworks.
ChannelSensing[Data-MFCorrelation]DatareceivingSynchronizationmessagereceiving[Control-MFCorrelation][SmallID]ClockCorrection[SameID]SynchronizationChange[LargeID][NoNeighbors]TheNewSynchronizationInformationTransmissionOvertheDataChanneltotheNeighbors[Neighbors]SynchronizationMessageTransmissionFigure1.
Theoperationoninitialsynchronization.
ofsuchanevent.
Thebenetisfasterconvergencerate(notethatthesynchronizationmessagesarenormallytransmittedonthepredenedratethroughthecontrolchannel[4]).
ThismethodisdescribedintheFigure1asanUML(UniedModelingLanguage)diagram.
Thestartingpointisthatthenodeissynchronizedtosomeofitsneighborsifanyexist.
Inaddition,thenodelistensboththedatachannelandthecontrolchannelsimultaneously.
Ifthesignalisencounteredformthecontrolchannel([Control-MFCorrelation])therearetwooptions:thesynchronizationmessageistransmittedbyanodethatbelongstothesamecluster([SameID])orthedataisfromanodeofanothercluster.
Inthelatterop-tiontherearetwopossiblecases:theNIDinthemessageissmaller([SmallID])andthemessageisignoredoritislarger([LargeID])andthereceivernodehastochangeitstiming.
Ifthereisnoneknownneighborsthenodejustchangesitstiming([Noneighbors]),butifthereare([Neighbors])theinformationaboutnewNIDanditstimereferenceistrans-mittedtotheneighborsbeforethenodechangesitstiming.
TheknowledgeaboutneighborhoodisbasedontheRule2,i.
e.
,nodecanexploittheinformationcollectedindirectlyfromthesurroundings.
ThisissueisfurtherdiscussedinthesectionsE.
andF.
C.
MergingRecognitionWithTheSameNetworkIDTheproblemofanetworkpartitioningandmergingcanbesubdividedintotwoslightlydifferentcases,namelythecaseofacommonNIDandthecaseofdifferentNIDs.
ThecasesaredescribedasGoal2andGoal3inthesectionA.
3of7ChannelSensingSynchronizationMessageTransmission[Data-MFCorrelation]DatareceivingSynchronizationmessagereceiving[Control-MFCorrelation]ClockCorrection[SameID]SynchronizationChange[LargeID][SmallID][LargeClockError][SmallClockError]DistributedDecisionMaking(aboutsynhchronizationchange)Figure2.
There-mergingrecognitionbythetiminger-rors.
TheprobleminsameNIDcasecanbeapproachedbysub-dividingtheproblemintothreestages:1.
Howtosepa-rateconfrontingsubnetworkswhenboth(all)havethesameNID2.
AfterthepresenceofequalNIDsubnetworksisde-tected,howtodecidewhichoneschangetheirtimingandwhichonenot3.
HowtoguaranteeunambiguousnetworkwidedecisionsaboutthetimingchangesTheNIDbasedhierarchyassuchdoesnotoffersolutionsimplybecausetheNIDsarethesameinbothmergingsub-networks.
However,iftheseparationtimeisnottoolongthereisnoneedforsubnetworkdistinguishingsincenetworktimesynchronizationalgorithmscanusuallyconvergequiterapidlyfromsmallmutualtimeerrors.
Thus,themaximumallowedseparationtimedependsoftheclockdriftrate.
Withidealclocksthisseparationtimewouldbeinnite.
There-fore,themethodproposedhereinisbasedonthetimedif-ferencecomparisonandthefactthatsmalltimingerrorscanbeignored.
Thus,alargetimeerrorbetweenthetimestampintheincomingmessage(withtheequalNIDs)andthelo-caltimebaseofthenodeisusedasametricfordeningaoccurrenceofasubnetworkre-merging.
ThefunctionalityisfurtherdescribedintheFigure2.
WhenanodereceivesasynchronizationmessagewiththesameNIDithas([SameID])itconductsatimingerrorcom-parison.
Ifthedifferenceissmall([SmallClockError])theconclusionisthatthemessageoriginsfromthesamesubnet-work.
Ifthetimingerrorislarge([LargeClockError])theconclusionisopposite,i.
e.
,themessagearrivesfromanothersubnetworkandadecisionabouttimingchangeisneeded.
ThedecisionmakingrulesarediscussedinthesectionE.
,ChannelSensingSynchronizationMessageTransmission[Data-MFCorrelation]DatareceivingSynchronizationmessagereceiving[Control-MFCorrelation][SameID][LargeID][SmallID]ClockCorrectionDistributedDecisionMaking(aboutsynhchronizationchange)InformingtheOtherNetworkAbouttheDecisionNottoChangetheSynchronization[NottoChange]InformingtheOwnNetworkAbouttheDecisiontoChangetheSynchronization(anordertotheneighbors)SynchronizationChange[ACKreceivedormaximumNumberofre-transmissionsdone][Change]ChannelSensing[else][NotaMergingCase][AMergingCase]Figure3.
Theoperationonthenetworkmerging.
whereasthecorrespondingactionsarepresentedinthenextsectionandintheFigure3.
Themethodassuchispronetoarepetitionjamming,i.
e.
,thesynchronizationmessagecouldberecordedandrepeatedbyaninterferer.
Asaconsequencethemethodwouldmakefalsedecisions,andthetimingconsistencywouldnotholdanymorewithinthenetwork.
Therefore,e.
g.
,runningpacketnumbering,multiplepacketreceivingbeforedecisionmak-ingortwodirectionalmessagingcouldbeconsideredasanantijammingmethods.
However,theseproblemsareleftasfutureresearchtopics.
D.
MergingRecognitionWithTheDifferentNetworkIDsThetwolatterproblemspresentedinthesectionC.
arerel-evantwhensubnetworkswithdifferentNIDsaremerging.
Furthermore,anewproblemisintroduced,namelyhowtodistinguishtheinitialsynchronizationcasefromthenetworkmergingcase.
Theinitialsynchronizationischaracterizedbyarapidtimingadaptation,i.
e.
,thelocaltimingofanodeischangedseveraltimesbeforeofconvergence.
Incontrary,beforeofannet-workmergingthere(usually)hasbeenasteady-statephase,i.
e.
,timingisne-tunedbutnotchanged.
Thisbehaviorcanbeexploitedwhenmakingsuchadecisionthatasynchro-nizationmessageisfromanothersubnetwork.
ThemethodispresentedintheFigure3.
Itshouldbeemphasized,how-ever,thatthereasonfortheinitialsynchronizationphaseanddifferentNIDmergingcasedistinguishingisthatintheini-tializationphasethemerenodeIDmethodisefcient[4]whereaswithmergingcaseitisanticipatednottobe[6].
4of7Thedecisionaboutamergingcaseprecedesmeasuringofhowlongthesametimesynchronizationhasbeenvalid.
Ifacertainthresholdvalue(notdeterminedherein)isexceedthecaseisdeclaredtobemerging([AMergingCase]).
WhenamergingcaseisdeclaredthedecisionrulespresentedinthesectionE.
areadopted.
Ifthethresholdisnotexceed,thedecisionisreversed([NotAMergingCase]).
Anyhow,ifitisdecidedthatthesynchronizationistobechanged([Change])]are-synchronizationmessageistransmittedtotheneighborsandanacknowledgement(ACK)messageiswaited.
Ifthedecisionisreversed([NottoChange])thiscouldbenotiedtotheothernetwork.
Theseissuesarefur-therdiscussedinthesectionI.
E.
DistributedDecisionMakingAfteranodehasdetectedtheoccurrenceofanetworkmerg-ingadecisionabouttimingchangehastobedone.
Asstatedearlierthedecisionmakingruleshavetotakeintoac-countthetransmissionblackout(withFHwaveform)orthemeretiminginaccuracy(withTWSN)withinthenetworkthatmakesthetimingchange.
Thisisduetothefactthatsimultaneoustimingchangeisnotpossiblewithinamulti-nodenetwork.
Takingthatintoaccountitwouldbefavor-abletochangethetimingwithinanetworkwithleastnum-berofnodesand/orleastdatatransferactivity.
Duetothedistributedcharacteristicsofanadhocnetworkitisnotal-waysarealisticassumptionthatthenodeshaveuptodateknowledgeaboutthenetworksizeordataactivity.
Togetevenclosetoreal-time-estimateofthoseparameterswouldpresumablerequirealotofcontroltrafc.
Inordertokeepthecontroltrafcmarginalitisstatedthatnodeshavetomakethedecisionsabouttheirnetworksizeanddataactiv-itydistributively,i.
e.
,basedontheirlocalvicinity.
Thisis,again,anexampleofthedesignprinciplesreferredinthesectionA.
Thenodescangatherinformationoftheirsur-roundingsbylistening,e.
g.
,MACmessages,likeRTS(Re-questToSend),CTS(ClearToSend)orroutingmessages,likeRREQ(RouteREQuest),RREP(RouteREPly)orbymeansofsynchronizationmessages.
ThetypesandamountoftheMACandroutingmessagesdependsontheusedpro-tocols.
Theotherrelevantinformationthatcouldbegath-eredistheamountofdatatransmittedeitherbythenodeitselforitsneighbors.
Thenodecaneasilykeeptrackoftheamountofthedataithasgenerated,receivedorrouted.
Fur-ther,forexamplewidelyinvestigatedIEEE802.
11standarddenesanDCF(DistributedCoordinationFunction)andas-sociated"virtualcarriersense"mechanismthatdenesanNAV(NetvorkAllocationVector)[16]thatcanbeeffec-tivelyusedindeterminingthedataactivityoftheneighbors.
Sinceboththeneighborinformationandthedataactivityinformationaregatheredindirectlyfromthesurroundingsthereisnotintroducedadditionalcontroltrafc.
Anyhow,theinformationgatheredispronetoloseitsrelevance,i.
e.
,becomeold.
Thisisduetothemobilitywhichchangesthetopologyand,e.
g.
,thedataactivitycanchange.
Therefore,theestimatesofthedecisionmakingmetricshavetobeup-datedoncontinuousmannerbymeansofthesynchroniza-tion,MACandroutingmessages.
F.
NeighborinformationInadditiontothatanodecankeeptrackofthenumberofitsinstantneighborsitcansendthisinformationtoitsownneighbors.
Thisinformationcanbeincludedinthesynchro-nizationmessage,andtherefore,thenodesattainaknowl-edgeabouttheirsurroundingscoveringtwohops.
Thiskindofmethodisusedalsoin[11].
Theneighborinformationcouldbeformulated,e.
g.
,by:Ld=Nn+coeffn*Na(2)andNa=Nni=1NiNn,(3)whereLdisanode'sestimationofthelocaldensityofthenetwork,Nnisthenumberofneighborsofanode,coeffnistheweightingtermfortheamountof2-hopneighbors(≤1)andNiisthenumberoftheneighborsoftheithneigh-bor.
Equation(2)givesthesumofthenode'sneighborsandweightedaverageof2-hopneighbors.
Thecoeffnisde-nedtobe≤1inordertogivethesmalleroratmostequalemphasistothenumberofthe2-hopneighbors.
G.
DataactivityLiketheneighborinformation,alsothedataactivityinfor-mationcanbetransferredfromneighbortoneighborbythesynchronizationmessages.
Thedataactivityinformationcanbeformulatedlikeinequations(2)and(3)La=Oa+coeffd*Nda(4)andNda=Nni=1NaiNn,(5)whereLaisanode'sestimationofthelocaldataactivityofthenetwork,Oaistheamountofdatathenodehastrans-ferredandrouted,coeffdistheweightingtermforthedata5of7activityof1-hopneighbors(≤1)andNaiisthedataactiv-ityoftheithneighbor(itsLavalue).
Equation(4)givesthesumofthenode'sowndataactivityandweightedaverageofthedataactivityof1-hopneighbors.
Theunitofthedataactivitydependsonthe,e.
g.
,theoreticaldatabandwidthofthesystemandhowlongthestatisticsarecollectedbeforedeclaredold.
Thesamerationalebehindthedenitionofcoeffd≤1isstatedaswithcoeffn,H.
DecisionmakingrulesThedecisionmakingmetricspresentedinsectionsF.
andG.
areusedbyanindividualnodewhenadecisionaboutthetimereferencechangeisneeded.
ThecomparisonismadeforthecalculatedLdandLavaluesofthereceivingnodeandcorrespondingvaluesinthereceivedsynchronizationmessage.
Therearemultiplealternativeshowthemetricscanbecompared.
Aconvenientalternativeisforexample:"CompareLdvalues.
Ifthevaluesareequal(orcloseto),compareLavalues.
"Thechoiceismadeinfavorofthenodewithlargervalues.
Inthatcasethelargernetwork(orthenodeoflargerdensityinitsvicinity)isalwayschosenastheonethatkeepsitssynchronizationandotherhavetochangetheirtiming.
Furthermore,thisfunctionalityisapplicabletoalateentrycasetoo,sinceanodewithoutneighborsandob-viouslywithoutanydataactivityisalwaysoverrunregard-lessofitsID.
OtherwisealateenteringnodewiththelargestIDcouldforcethenetworktochangeitstimereference[6].
I.
ConsistencyoftheDecisionsTherstprincipleofthedesignofaselforganizinginfor-mationnetworkispresentedinthesectionA.
astheRule1.
Thegoalistodesignsuchdecisionrulesthatleadtoanetworkwideconsistentandintendedoutcome.
Further-more,thedecisionrulesshouldbedesignedtobesuchthatanindividualnodecould,byobeyingthem,makeanetworkwide(intended)decisions.
IfFHorjustthenetworktimingareconsidereditwouldmeanthatthewholenetworkwouldmakethesamedecisionaboutchangingtheFHcodephaseorjustthetiming.
DuetothefactthatLdandLametricsaredeterminedlocallythevalueswillbedifferentdepend-ingonthenode.
Asaconsequence,thedecisionthatthenodesmakearenotnecessarilyconsistentwithinanetwork.
Thiswouldbeemphasizedwhentwo(ormore)equallysizedandequallyactivenetworksaremerging.
Nevertheless,thedecisionsshouldbethesamethroughoutthenetworks.
Inordertoguaranteetheconsistencyofthedecisionmak-ingthedecisionsareproposedtobecentralizedtemporary.
123Transmissionrange12344MovementNetworkXNetworkYThesizeofthenetworkYisalteredbyremovingthenodesinnumberedorder.
Forexample,for13nodesvs.
11nodesscenario,nodesnumberedasonesareremoved,etc.
NID:12NID:25Figure4.
Thesimulationsetup.
Therefore,thenodethatistherstonetoreceiveasyn-chronizationmessagefromanothernetworkmakesthedeci-siononbehalfofthewholenetworkitbelongsto.
Thenodethatmadethechangingdecisionbroadcasts(ormulticasts)amessagetoitsneighbors.
Themessageisanordertochangethetiming,andthus,nodecisionmakingsareconductedbythenodesthatreceivethemessage.
Besidestheinformationofferedtotheneighborsthemessagecouldactasaninfor-mationsourcefortheanothernetworkthatanewnetworkismergingtoit.
Intheoppositecasewhenthenewsyn-chronizationisdecidedtobeignoredthenodethatmadethedecisioncoulddonothingorinformtheothernetworkaboutitsdecision.
Thisdecisioncouldalsobeconsideredbind-ingfortheothernetwork,sinceitwouldfurtherenhancetheconsistencyofthedecisions,i.
e.
,extendittointernetworkwide.
TheUMLchartpresentedinFigure3describesthefunctionality.
IV.
SIMULATIONS010203040506070809010011000,10,20,30,40,50,60,70,80,91coeff_nProbabilitythatnetworkYchangesthetiming(%)X(13)VS.
Y(13)X(13)VS.
Y(11)X(13)VS.
Y(9)X(13)VS.
Y(7)X(13)VS.
Y(5)Figure5.
TheprobabilitythatthenetworkYchangesthesynchronizationasafunctionofcoeffn.
Fivesimulationscenarioswereformulatedinordertoin-vestigateboththefunctionalityofthedistributeddecisionmakingandtheconsistencyofthedecisions,i.
e.
,doesthealgorithmfavorthelargernetworkanddoesthemergednet-workconvergetoasametimebase.
Thescenariosareout-linedintheFigure4andcorrespondstoa"differentNID"6of7-caseinthesectionD.
Thesimulationresultsforthedis-tributeddecisionmakingbasedonLdparameteraregivenintheFigure5where,e.
g.
,X(13)vs.
Y(5)correspondstoacasewherenodesmarkedas1-4intheFigure4areremovedfromthenetworkY,etc.
Theprobabilitythatasmallernet-workchangesitstimingasafunctionofcoeffnissimulatedwithOPNET.
Theresultsconrmthatwhenthedecisionisbasedon2-hopneighborinformation,i.
e.
,coeffn>0,thesmallernetworkhasahigherprobabilitytochangethesyn-chronization.
Adivergentresultisobtainedwhenonlyone-hopneighborinformationisawailable(coeffn=0):thesynchronizationischangedabout50%probabilitybyei-therofthenetworkswhennetworkYhas13,11or9nodes.
Thisisduetothefactthatinthosecasesone-hopinforma-tiondoesnotincludeanotionofthenodesmarkedas1and2.
Furthermore,theconvergenceofthedistributeddecisionswasseparatelyconrmedtoholdsinceacommonNIDwaschoseninallthesimulationscenarios(notshownintheFig-ure5).
TheLaparameterinvestigationsandsimulationsareleftasfuturetopicsdueboththespacelimitationsofthepaperandthefactthatLametric'smorecomplexformationjustiestotallynewandcomprehensivescenarios.
However,itisanticipatedthatequalorclosetoequalresultswouldbeachievedwithLametricaswithLdmetricinthesepartic-ularstudiedscenarios.
V.
CONCLUSIONSInthispaperthenetworktimesynchronizationproblemwasinvestigated,inparticularlyfromtheviewpointofFHadhocandtimingsensitivesensornetworks.
Apropositionsforthreeforeseenspecialproblemcaseshasbeengiven,namelyforlate-entrynodes,samenetworkIDmergingcaseanddifferentnetworkIDmergingcase.
Thepropositionstakeadvantageofindirectlygatheredinformationfromthesurroundings,likethenumberofneighbors,i.
e.
,localden-sityandalocaldataactivity.
Therefore,itispossibletotakeintoaccountboththesizeestimateanddataactivityestimateofthenetworkswhendecidingwhich(sub)networkchangesthetiming,andaccordingly,suffersthepossibledatatrans-missionblackoutortimereferenceasynchronismduringthere-timingphase.
Thedecisionsaremadedistributively,i.
e.
,withoutcentralentityorinfrastructuralintervening.
Simu-lationresultsofthedecisionmakingbasedonLdparameteraregiven.
Theresultsshowthattheparametercanbeeffec-tivelyusedasadecisionmetric.
Thefutureworkwillcon-sidercomprehensiveLametricsimulations,simulationwithrandomlyshapednetworkclustersandsimulationsagainstintentionaljamming.
ACKNOWLEDGEMENTSThisworkwassupportedbytheScienticAdvisoryBoardforDefence(project41/MDD707/06).
ThecontributionofJuhaHuovinentothesimulationmodelisgreatlyappreci-ated.
REFERENCES[1]JarmoProkkolaandTimoBr¨aysy,"Bi-codechannelaccessmethodforadhocnetworks,"inIEEEproc.
ofSpreadSpectrumTechniquesandApplications,2004.
[2]JoshBroch,DavidA.
Maltz,DavidB.
Johnson,Yih-ChunHu,andJorjetaJetcheva,"Aperformancecomparisonofmultihopwire-lessadhocnetworkroutingprotocols,"inIEEEProceedingofIEEE/ACMMOBICOM,1998.
[3]HarriSaarnisaari,"Analysisofadiscretenetworksynchronizationalgorithm,"inIEEEProc.
ofMilCom,2005.
[4]TeemuVanninen,HarriSaarnisaari,MattiRaustia,andTimoKoskela,"FH-codephasesynchronizationinawirelessmulti-hopFH/DSSSadhocnetwork,"inIEEEProc.
ofMilCom,October2006.
[5]MKochhal,LSchwiebert,andSGupta,"Role-basedhierarchicalselforganizationforwirelessadhocsensornetworks,"inACMProc.
ofWSNA,September2003.
[6]TeemuVanninen,TimoBr¨aysy,andMattiRaustia,"Enhancedper-formanceintacticaladhocnetworks–technologyenablersandso-lutions,"inProceedingsofMilitaryCISConference(MCC).
Bonn,Germany,25.
–26.
September2007.
[7]AKarnikandAKumar,"Distributedoptimalself-organisationinadhocwirelesssensornetworks,"IEEE/ACMTransactionsonNet-working,vol.
15,no.
5,October2007.
[8]JZhang,KPremaratne,andPHBauer,"Adistributedself-organizationalgorithmforad-hocsensornetworks,"inIEEEProc.
ofWCNC,2003.
[9]VSBorkarandDManjunath,"Distributedtopologycontrolofwirelessnetworks,"inIEEEProc.
ofWIOPTSymbosium,2005.
[10]CHOu,KFSsu,andHCJiau,"Connectingnetworkpartitionswithlocation-assistedforwardingnodesinmobileadhocenviron-ments,"inIEEEProceedingsofPacicRimDependableComput-ingSymposium,2004.
[11]HRitter,RWinter,andJSchiller,"Apartitiondetectionsystemformobilead-hocnetworks,"inIEEEProc.
ofSECON,October2004.
[12]E.
DKaplan,UnderstandingGPSPrinciplesandApplications,ArtechHouse,Inc.
,England,1996.
[13]ZTangandJJGarcia-Luna-Aceves,"Hop-reservationmultipleaccess(hrma)forad-hocnetworks,"inIEEEProc.
ofINFOCOM,March1999.
[14]CPrehoferandCBettstetter,"Self-organizationincommunicationnetworks:principlesanddesignparadigms,"IEEECommunica-tionsMagazine,vol.
43,no.
7,July2005.
[15]NChatterjee,APotluri,andANegi,"Aself-organizingapproachtomanetclustering,"inInternationalConferenceOnHighPerfor-manceComputing(HiPC),BangaloreIndia,December2006.
[16]"Ieeestd.
802.
11-part11:Wirelesslanmediumaccesscontrol(mac)andphysicallayer(phy)specications,"1997.
7of7