基于无线Ad-Hoc网络的一种新的分布式电源高效拓扑控制算法(IJCNIS-V5-N12-3)

I.J.ComputerNetworkandInformationSecurity,2013,12,20-26PublishedOnlineOctober2013inMECS()DOI:10.5815/ijcnis.2013.12.03Copyright©2013MECSI.J.ComputerNetworkandInformationSecurity,2013,12,20-26ANewDistributedandPower-EfficientTopologyControlAlgorithmforWirelessAd-HocNetworksSaeidTaghaviAfshordandBagerZareiComputerEngineeringDepartment,ShabestarBranch,IslamicAzadUniversity,Shabestar,Iran{taghavi,zarei.bager}@iaushab.ac.irBahmanArastehComputerEngineeringDepartment,TabrizBranch,IslamicAzadUniversity,Tabriz,[e-mail]—Toguaranteetheperformanceofadhocnetworks,utilizingahierarchicalarchitecturemodelisnecessary.Aninstanceofthisstructureisclustering.Inthispaperacluster-basedtopologycontrolalgorithmisproposedwhichbuildsanenergy-efficientandalowinterferencetopology.Ituseslow-qualityinformation,exchangesafewmessages,anddoesnotneedforextrahardwareequipmentaswell.Itisalsosuitableforpracticaluse,becauseintheimplementationofthisalgorithmisnotneededtoknowthelocationorthedirectioninformationofthenetworknodes.Soitispossibletoclassifythisalgorithmasaneighbor-basedtopologycontrolalgorithm.Inaddition,forthetransmittingandthemaintainedpowerlevelsofeachnode,amodificationisappliedaccordingtotherealhardwareplatforms.Itimprovestheenergyconsumptionintheidealconditions.IndexTerms—Adhocnetworks,clustering,topologycontrol,energyconsumptionI.INTRODUCTIONInmobilead-hocnetworks(MANETs),allthenodesarecooperatingtoachieveforaglobalspecifiedtask,suchasareamonitoringanddatagathering.Itisimportanttomakeanappropriatetransmissionpowerselectionforeachnode,toreduceenergyconsumptionandsignalinterference.Thisiscalledtopologycontrol(TC),whileitisstillsatisfyingthecertainglobalconstraints[1].Intheshorterdefinition,topologycontrolistodeterminethetransmissionpowerofeachnodesoastomaintainnetworkconnectivityandconsumetheminimumtransmissionpower[2].AtleasttwoissueshavemotivatedtheresearcherstostudytherealmofTCtechniques:reducingtheenergyconsumptionandincreasingthenetworkcapacity[3].ATCalgorithmtendstomanagethelogicalcommunicationofthenetworknodestowardthemaximumtransmittingrange.Itdealswiththeoptimizationofthepowerconsumptionwhilekeepingthenetworkconnected.Thenodesmobilityandupdatingtheirinformationarethemostimportantproblemsinwirelessadhocnetworks;becausewithmovingasinglenode,theinformationofallthenodeswouldbeupdated.Sooptimizingtheenergyusageinthesenetworksisessentialforeachnodeandforthewholenetwork,aswell[4].ThedistributedTC,especiallyneighbor-basedTCprotocolsaremoresuitabletotheimplementationinmobileadhocnetworks[3].Thepaperisorganizedasfollows.ThebasicconceptsareintroducedinSection2.Themostsimilarandwell-knownprotocol,KNEIGH,forcomparisonpurpose,isbrieflypresentedinSection3.InSection4,theproposedprotocolalongwithsimulationandexperimentalresultsisexplainedindetails.Section5concludesthepaperanddiscussesabouttheachievedproperties.II.BASICCONCEPTSA.ApropositionfromgraphtheoryProposition.Let{,,...,}12Sxxxn=beasetofpointsintheplanesuchthatthedistancebetweenanytwopointsisatleastone.Showthatthereareatmost3npairsofpointsatdistanceexactlyone[5].Proof.DefinegraphGonspaceSasfollows:thesetofpoints12,,...,nxxxbeasV(G),andtwoarbitraryanddistinctverticesixandjxfromV(G)isadjacentifandonlyifthedistancebetweenthembeexactly1.Clearly,thiskindofedgeswillconstructE(G).Itisenoughtoprovethatforeachvertexxi(1)in≤≤,()6idx=(thatis,thedegreeofvertexxiisequalto6).Becauseitmeansthat,eacharbitraryvertexxihasbeenlinkedatmostwith3pairsofV(G)atdistanceexactly1.WithconsideringtheallofnverticesofG,theassertionwillbeestablished.ANewDistributedandPower-EfficientTopologyControlAlgorithmforWirelessAd-HocNetworks21Copyright©2013MECSI.J.ComputerNetworkandInformationSecurity,2013,12,20-26Forthat,drawanimaginarycirclewithradius1centeredatxi.Accordingtotheassumption,itisclearthatanyvertexofGdoesnotexistinsidethecircleandaccordingtothedefinitionofG,anyadjacentvertexwithxicannotbeattheoutsideofthecircle,andifavertexofGisonthisimaginarycircle,itshouldbeadjacentwithxi.WeshowthatatmostsixverticesofGcanbesituatedonthecircle.Letthevertices126,,...,iiixxxhavesuchproperties.Thisisfeasibleandthereasonisasfollows.Supposethatthesesixverticeshavebeensituatedinequaldistancesand,withoutlossofgenerality,theyareonthecircleatthementionedorder.Thecentralangeloftwoadjacentvertices(forexamplexi1andxi2)ofthiscirclewillbe360/660=andconsequently12iiixxxwillbean60degreeangle.Thereforthetriangle12iiixxxisequilateralandthusthedistancebetween1ixand2ixisexactlyequalto1.Itisevidentthatthedistancebetweentwonon-adjacentverticesonthecircleisgreaterthan1.Sotheexistingofsixverticesonthiscircleispossible.Ifthearbitraryvertexkxisalsosituatedonthesupposedcircle,usingthesimplegeometricalcalculations,itisobtainedthatthedistancebetweenatleasttwoverticesofthesesevenverticeswillbelessthan1,whichisacontradiction.B.ClusteringClusteringalgorithmsorganizethenetworkintoasetofclusters,whichareusedtofacilitatetheroutingoperationsbetweennodesand/ortobetterbalancetheenergyconsumptioninthenetwork.Cluster