基于稳定性控制的自适应MANET分簇策略.pdf 14页

'中国科技论文在线http://www.paper.edu.cn基于稳定性控制的自适应MANET#分簇策略*张沪寅，郝圣，刘华俊，宋梦凯5（武汉大学计算机学院，武汉430079）摘要：（1）移动无线AdHoc网络是一种由若干移动性节点组成的，不依赖于任何固定设备的临时网络。在移动无线AdHoc网络中，频繁的节点移动、不佳的节点分布将减少簇的生存时间，并增加通信开销，而这些问题会降低簇的稳定性。针对上述问题，本文提出了基于稳定性控制的自适应MANET分簇策略(SCA)。在文中，我们首先推导出簇的期望生存时10间模型与簇的可靠性通信度量模型。在此基础上，我们设计了簇首的稳定性度量模型进行簇首选择。此外，我们同样给出了分簇的维护机制。实验结果表明，本文提出的分簇策略在稳定性指标方面有很好的表现，并在一定程度上降低了通信开销。关键词：移动无线AdHoc网络；分簇；期望生存时间；可靠性通信度量；维护机制中图分类号：TP311DOI号：15AnadaptiveclusteringstrategyforMANETbasedonstabilitycontrolZhangHuyin,HaoSheng,LIUHuajun,SONGMengkai(ComputerSchool,WuhanUniversity，Wuhan430079)20Abstract:MobilewirelessAdHocnetwork(MANET)isatemporarynetwork，whichiscomposedofanumberofmobilenodesanddonotdependonanyfixedequipment.InMANET，frequentnodemotion、badnodedistributionwillreducetheclusters’survivaltime、communicationqualityandincreasethecommunicationoverhead.Alloftheseproblemswilldecreasethestabilityofclusters.Focusingontheseproblems,weputforwardanadaptiveclusteringstrategyforMANETbasedon25stabilitycontrol(SCA).Firstly,wederivethecluster’sexpectedsurvivaltimemodelandreliablecommunicationmetricmodel.Basedonthesetwomodels,wedesignthecluster’sstabilitymetricmodelasthemeasurableindicatorofclusterheadselection.Besidesthat,wealsogiveamaintenancemechanismofclustering.Theexperimentalresultsshowthatourproposedclusteringstrategyhasgoodperformanceonstabilityindicators.Besidesthat,itcanreducethecommunicationoverheadinsome30degree.Keywords:MANET;clustering;expectedsurvivaltime;reliablecommunicationmetric;maintenancemechanism0引言35移动无线AdHoc网络(MANET)是由一组不依赖于固定通信网络设施的无线移动节点[1]组成，能够快速形成网络体系并提供重要通信与服务的临时网络。MANET具有多跳路由，节点能量有限，无线通信环境不可靠，动态拓扑快速变化等特性。为了提高MANET的可扩展性，分簇是一种十分重要与常见的策略。采用分簇策略后绝大多数节点的信息交换次数会[1]降低，因此节点路由信息维护开销也将降低，此外网络规模也可以在一定程度上得到增大，40并可保证网络管理与控制的高效性。基金项目：高等学校博士学科点专项科研基金(No.20130141110022)；高等学校博士学科点专项科研基金(No.20130141120021)作者简介：张沪寅，男，1962年生，工学博士，教授,主要研究领域为highperformancecomputing,networkqualityofservice,newgenerationnetworkarchitecture.E-mail:zhy2536@whu.edu.cn-1- 中国科技论文在线http://www.paper.edu.cn分簇的基本思想就是按照位置的远近关系将网络的节点分成若干集群，以便于管理。在一个簇内,部分节点负责建立分簇并且维持网络拓扑的稳定性，这样的节点也被称作簇首节点，簇首节点的集合构成一个支配集。簇内的节点一般被划分为普通成员节点与协助簇间通[2]信的网关节点，即簇首节点之间不进行直接的信息交换。一般的MANET分簇算法根据某45些本地条件或者AdHoc网络的属性(例如节点密度、移动性、权重、剩余能量等因素)将节点加入到簇首节点集合之中。现有的分簇机制中往往忽视了节点分布、节点频繁变动对分簇稳定性的影响，且以上工作虽考虑到多种参数对分簇的影响，但多采用观测值的方法，缺乏严谨的推导模型来进行簇首选择判定。因此本文有必要设计新的理论化簇首选择判定模型。此外，现有的分簇算法中未考虑如何维护调整动态网络环境下的分簇结构。因此，本文还需50给出相应的分簇维护机制以保证分簇结构的调整。本文的主要贡献在于以下三个方面：(1)我们提出了簇的期望生存时间模型，保证分簇在动态环境下具备更高的稳定性，即提高了簇的生存时间。(2)我们给出了簇的可靠性通信度量模型，提高了动态环境下的通信可靠性，并降低了成员节点与簇首节点的更新次数与随之带来的通信开销。(3)本文给出了分簇的维护机制，以保证分簇结构的有效调整。551相关工作近年来，国内外学者对MANET分簇算法进行了大量研究并取得了丰富的成果。目前，[3]关于MANET分簇算法的研究仍然热门且富有创造性。ChatterjeeM在文献中提出了WCA算法，这是一种按需的，分布式的，综合考虑多种因素的加权分簇算法。但该算法并未考虑到节点的分布差异对分簇结果的影响，且该算法对移动性与场景的参数设置十分敏感。[4]60Piyalikar在WCA算法的基础之上设计了一种带有预测机制的分簇算法(FCA)。该方法通过设置平滑因子函数对节点的簇首变化进行预测，避免了不必要的簇首选择发生。[5]在文献中，SinghalS提出了基于模糊理论的分簇算法。该算法能够较好的减小时间开销与分簇代价，并在一定程度上提高了簇的稳定度。该算法对分簇规模的定义非常严格，且在高速环境下性能较差。[6]65OhYJ在文献中提出一种基于多移动属性度量的分簇算法(MPCA)。在文中，作者设计了一种基于移动性测度的簇首交换概率函数，并通过该函数降低簇首节点更迭的次数，尽可能地提高分簇的稳定性。[7][8]在文献中，BentalebA提出了信任度的概念以保证簇结构的稳定性，并在文献中利用多普勒平移法与改进的信任度定义构建了一种分簇机制(TVCA)。该方法通过监督簇的安[9]70全级来提高分簇的稳定性。之后，作者在文献中提出了适用于大规模网络的分簇算法。该算法可保证稀缺带宽资源的合理分配却不再考虑分簇的稳定性控制。[10]TolbaFD设计了一种高速动态环境下的分簇算法，该算法可在节点移动速度很大且节点密度较大的情况下得到理想的簇首节点个数与较好的分簇效率，但是在稀疏环境下的效果并不理想。此外，作者并未考虑到在获取良好分簇结构的情况下如何保证簇的稳定性。[11-15]75在文献中，作者将问题场景设置为能量敏感性型AdHoc网络。通过设计不同的节[12-14]点的能量损耗估算模型以保证被选择的簇首节点相对其他节点具备更多的剩余能量，而[11,15]文献则通过仿真观测的方式获取最大剩余能量以反映节点的生存时间作为簇首判定准则。在实际场景中，节点的生存时间较长，因此相对于节点剩余生存时间对网络连通性的影-2- 中国科技论文在线http://www.paper.edu.cn响，节点分布、稀疏程度、场景规模等因素往往对连通性具有更重要影响。[16-17]80文献分别讨论了具有分簇结构的MANET路由算法的效能问题,即如何设置分簇策略以降低传输能耗。[3,5-9,12-16]本文注意到现有文献中提出的分簇算法并未很好的考虑到以下问题：(1)划分后的簇结构稳定性对分簇效率的影响，即短暂的成簇时间会导致簇首节点与成员节点的频繁更迭，而由此带来的通信开销亦会增大；(2)簇内节点分布会对簇的通信质量与通信开销产生85影响，间接影响了簇的稳定性；(3)缺乏严谨的簇首判定模型，且将节点设置为快速能量衰竭方式并不符合实际情况(实际情况中节点的生存周期为数周至数月远大于仿真模拟时长)。基于以上事实与文献中存在的缺陷，本文设计了一种适用于非能量敏感场景下的簇首稳定性度量模型，这其中包括了簇的期望生存时间模型、簇的可靠通信开销模型。通过以上两种模型构建簇首判定准则来选择簇首。此外，如何保证在动态环境下有效地调整分簇结构也是需90要考虑的问题，因此我们同样在文中给出了分簇的维护机制。本文的剩余工作由以下三个部分组成：在第二部分我们将给出系统模型，其中包括了AdHoc网络模型、簇首的稳定性度量模型(包括簇的期望生存时间模型与簇的可靠性通信度量模型)，分簇维护机制；第三部分我们将进行仿真实验并对实验数据进行分析；第四部分是本文的结语与未来工作展望。95系统模型1.1AdHoc网络模型[18]根据图论知识可知，平面AdHoc网络可以用一张无向图来表示，即G=(V,E)。其中V代表了节点v的集合，E表示由所有链路e组成的集合。一般情况下节点的个数恒定，ii即V的势保持不变，但E的势随着链路的建立和删除发生改变。因此也可将分簇称作受到100额外限制的图形分割问题。由于基本图没有表现出任何规则形结构，所以根据一定参数对图[11]形进行分割就成为一个NP-Hard问题。分簇策略主要关心的问题是如何寻找支配集即最佳簇首集合：S⊆V(G)，使得N[v]=V(G)成立。其中N[v]表示节点v的相邻区域，可定iiv∈S义为N[v]={dist(v,v)0。因此可得出P(x)是一个严格的单调增函数，即随着节点losslossπ165之间距离的增大，丢包率上升通信质量下降。(1)继续对P(x)求一阶导数可得loss2(2)4ab−(bx−c)2P=e⋅(c−bx)(10)lossπcc其中，x=为P(x)的拐点横坐标值。当x∈(0,]时，P(x)缓慢增大，通信质量缓losslossbb-5- 中国科技论文在线http://www.paper.edu.cnc慢降低；x∈(,+∞)时，P(x)快速增大，通信质量快速衰减。lossb170基于上述推导，本文可对簇的结构进行分层处理(图1所示)并做出如下合理假设：当成员节点处在(0,r]时，簇首节点与成员节点的通信质量处在可接受范围内即不产生通信风险；反之，当成员节点处在[r,R)时通信质量发生快速衰减，产生通信风险。Rrrisk_region图1簇的分层结构rrBCRAFHKDERIJ175图2节点分布对通信的影响(a)图3节点分布对通信的影响(b)图2,3给出了此时簇成员节点分布不同导致通信质量不同的示例。如图2,3所示，A、F分别为簇的簇首节点，距离簇首节点A、F距离之和分别为D=|AB|+|AC|+|AD|+|AE|，D=|FK|+|FH|+|FI|+|FJ|。若D=D，则以A为簇AFAF180首的四个成员节点全部落入通信质量可接受的区域范围内，而以F为簇首的簇的四个成员节点中有2个节点中落入通信质量快速衰减的区域范围内。此时两个簇虽然具有相同的距离属性与密度属性测度，却产生不同的通信属性测度。为了形式化的描述此时节点分布不同对通信质量产生的影响，本文将通信风险概率分布函数定义为if(0TVCA)。不难发现FCA算法所得的平均簇首节点个数变动差异最大。用最大携带成员个数()2ln(N)衡量五种算法可知，本文提出的算法(SCA)与其余三种分簇算法都可保证成员节点个数小于最大携带成员个数。-9- 中国科技论文在线http://www.paper.edu.cn252015SCAWCAaveragenumberofclusterheadsFCATVCA101015202530maximumvelocity图5平均簇首节点个数vs移动速度280图5描述了在RandomWaypoint模型下，节点总个数为50，平均簇首节点个数与移动速度的关系。从图中可知，平均簇首个数不会随最大移动速度的增加而增大或减少，而是呈现一种小幅度浮动状态。本文算法(SCA)所得的平均簇首节点个数总体上多于WCA算法与FCA算法(FCA>WCA)，少于TVCA。(2).成员节点更新频度1000800600400SCA200WCAchangeofclustermembernodesFCATVCA05060708090100285numberofnodes图6成员节点更新频度vs节点个数图6描述了在RandomWaypoint模型下，最大移动速度为10m/s，成员节点累积更新次数与节点总个数的关系。如图所示，成员节点累积更新次数会随着节点个数的增加而增大，但不具有严格的线性关系。在RandomWaypoint模型中，本文提出算法(SCA)所得的成员节290点累计更新次数最小。以本文提出的算法(SCA)作为基础进行对比，WCA、FCA、TVCA的成员节点累积更新次数平均增多了45.6%、8.1%、37.5%。800600400200SCAWCAchangeofclustermembernodesFCATVCA01015202530maximumvelocity图7成员节点更新频度vs移动速度-10- 中国科技论文在线http://www.paper.edu.cn图7描述了在RandomWaypoint下，节点总个数为50，成员节点累积更新次数与移动295速度的关系。如图所示，成员节点累积更新次数会随着最大移动速度的增加而增大，但不具有严格的线性关系。本文提出算法(SCA)所得的成员节点累计更新次数整体上最小。以本文提出的算法(SCA)作为基础进行对比，在Randomwaypoint模型中，WCA、FCA、TVCA的成员节点累积更新次数平均增多了60.1%、11.2%、33.6%。(3).支配集更新频度400300200SCA100changeofclusterheadnodesWCAFCATVCA05060708090100300numberofnodes图8支配集更新频度vs节点个数图8描述了在RandomWaypoint模型下，最大移动速度为10m/s，簇首节点累积更新次数与节点个数的关系。如图所示，簇首节点累积更新次数会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法(SCA)作为基础进行对比，在Randomwaypoint305模型中，WCA、FCA、TVCA的簇首节点累积更新次数平均增多了38.9%、18.3%、20.1%。400300200SCA100WCAchangeofclusterheadnodesFCATVCA01015202530maximumvelocity图9支配集更新频度vs移动速度图9描述了在RandomWaypoint模型下，节点总个数为50，簇首节点累积更新次数与移动速度的关系。如图所示，簇首节点累积更新次数会随着最大移动速度的增加而增大，但310不具有严格的线性关系。以本文提出的算法(SCA)作为基础进行对比，在Randomwaypoint模型中，WCA、FCA、TVCA的簇首节点累积更新次数平均增多了47.8%、15.2%、26.8%。(4).节点通信负载-11- 中国科技论文在线http://www.paper.edu.cn0.200.180.160.140.120.100.080.06SCAWCAmessagespernodeandsecond0.04FCA0.02TVCA0.005060708090100numberofnodes图12节点通信负载vs节点个数315图12描述了在Randomwaypoint模型下，最大移动速度为10m/s，单位时间平均每个节点发送信息数量与节点个数的关系。如图所示，单位时间平均每个节点发送信息数量会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法(SCA)作为基础进行对比，在Randomwaypoint模型中，WCA、FCA、TVCA的节点单位时间发送信息数量平均增多了35.0%、5.2%、23.9%。0.200.150.10SCA0.05WCAmessagespernodeandsecondFCATVCA0.001015202530maximumvelocity320图13节点通信负载vs移动速度图13描述了在Randomwaypoint模型下，节点总个数为50，单位时间平均每个节点发送信息数量与移动速度的关系。如图所示，单位时间平均每个节点发送信息数量会随着节点个数的增加而增大，但不具有严格的线性关系。以本文提出的算法(SCA)作为基础进行对比，325在Randomwaypoint模型中，WCA、FCA、TVCA的节点单位时间发送信息数量平均增多了44.6%、2.3%、21.8%。分析以上实验数据组，本文可得出如下的结论：(1).若用理想簇首节点个数(实现分簇全覆盖的最少簇首节点个数)衡量分簇效率，本文算法SCA得到的簇首个数指标并未获得最佳的分簇效率。330(2).从支配集与成员节点更新频度的实验数据对比可知，本文提出的SCA算法能够有效地降低节点的更新频度，显著地提高了分簇结构的稳定性，这也说明了本文提出的簇首稳定性度量模型具有正确性。(3).簇首选择与频繁地节点更迭都会增加节点交换信息的数量，增加通信开销。从节点通信负载实验数据对比可知，本文提出算法(SCA)的通信负载指标优于其余算法，即有效地335减少了系统的通信开销，也说明了本文提出的簇首稳态度量模型与分簇行为认知机制是实际可行的。-12- 中国科技论文在线http://www.paper.edu.cn3结论分簇是一种提高动态网络可扩展性与拓扑稳定性的重要方法。现有MANET分簇算法中往往未考虑到节点分布差异与频繁的节点状态更迭对分簇稳定性的影响。基于以上事实，本340文提出了基于稳定性控制的MANET分簇策略(SCA)。在文中，我们提供了明确的研究步骤：①通过构建簇的期望生存时间模型与簇的可靠性通信度量模型,我们给出了一种新的簇首稳定性度量模型进行簇首选择；②我们同样给出了分簇的维护机制，以保证动态网络环境下分簇结构的有效调整。实验结果证明本文提出的分簇算法能够有效地改善分簇的稳定性，并减少节点的通信负载。345本文的研究结果为后续设计具有分层结构的路由协议提供了良好的拓扑稳态控制机制。在未来的研究中，我们认为如下的研究是有价值的：Ⅰ借助动力学理论与非线性控制论研究具有复杂网络行为的MANET分簇策略；Ⅱ构建一种基于本文分簇策略的分层路由机制。350[参考文献](References)[1]ChenLin-Xing.MobileAdHocnetwork--thetechnologyofwirelessself-organizingnetwork.Beijing:ElectronicIndustryPress,2008.(陈林星.移动Adhoc网络--自组织分组无线网络技术.北京：电子工业出版社,2008)[2]ChenK,ChenL,MaoJ,etal.AMultipleMetricsGatewaySelectionAlgorithmforVehicularAdHoc355NetworksinFadingChannels[C]//NinthInternationalConferenceonComputationalIntelligenceandSecurity.Leshan,China2013:648-652.[3]ChatterjeeM,DasSK,TurgutD.Anon-demandweightedclusteringalgorithm(WCA)foradhocnetworks[C]//GlobalTelecommunicationsConference.GLOBECOM"00.IEEE.SanFrancisco,USA2000:1697-1701.360[4]Piyalikar,KarP,BarmaMKD.ForecastWeightedclusteringinMANET[J].ProcediaComputerScience2016(89):253-260.[5]SinghalS,DanielAK.ClusterHeadSelectionProtocolunderNodeDegree,CompetenceLevelandGoodnessFactorforMobileAdHocNetworkUsingAITechnique[C]//FourthInternationalConferenceonAdvancedComputing&CommunicationTechnologies.IEEEComputerSociety,Rohtak,India.2014:415-420.365[6]OhYJ,LeeKW.AClusteringAlgorithmBasedonMobilityPropertiesinMobileAdHocNetworks[J].InternationalJournalofDistributedSensorNetworks,2015:1-15.[7]BentalebA,BoubetraA,HarousS.SurveyofClusteringSchemesinMobileAdhocNetworks[J].Communications&Network,2013(05):8-14.[8]BentalebA,HarousS,BoubetraA.AWeightBasedClusteringSchemeforMobileAdhocNetworks[C]//370ProceedingsofInternationalConferenceonAdvancesinMobileComputing&Multimedia.NewYork,USA.2013:161-166.[9]BentalebA,HarousS,BoubetraA.Anewtopologymanagementschemeforlargescalemobileadhocnetworks[C]//Electro/InformationTechnology(EIT),2015IEEEInternationalConferenceon.IEEE,Dekalb,USA.2015:31-37.375[10]TolbaFD,MagoniD,LorenzP.AStableClusteringAlgorithmforHighlyMobileAdHocNetworks.[C]//SystemsandNetworksCommunications,2007.ICSNC2007.SecondInternationalConferenceon.IEEE,CapEsterel,FrenchRiviera,France.2007:11-11.[11]AfsarM,Tayarani-NM,AzizM.Anadaptivecompetition-basedclusteringapproachforwirelesssensornetworks[J].TelecommunicationSystems,2015:1-24..380[12]KawadiaV,KumarPR.PowerControlandClusteringinAdHocNetworks[J].Infocom,2003,1:459--469.[13]ZhuT,ZhongZ,HeT.Energy-synchronizedcomputingforsustainablesensornetworks[J].AdHocNetworks,2013,11(4):1392-1404.[14]FathiA,TaheriH.Enhancetopologycontrolprotocol(ECEC)toconserveenergybasedclusteringinwirelessadhocnetworks[C]//ComputerScienceandInformationTechnology(ICCSIT),20103rdIEEEInternational385Conferenceon.IEEE,Beijing,China.2010:356-360.[15]El-BazzalZ,KadochM,AgbaBL.AFlexibleWeightBasedClusteringAlgorithminMobileAdhocNetworks.[C]//SystemsandNetworksCommunications,2006.ICSNC"06.InternationalConferenceon.IEEE,Tahiti,France.2006:50-50.[16]SenS,KarmakarD,SetuaSK.Anpowerefficientalgorithmfordistributedad-hocclusterbasedWireless-13- 中国科技论文在线http://www.paper.edu.cn390SensorNetworks[C]//Computer,Communication,ControlandInformationTechnology(C3IT),2015ThirdInternationalConferenceon.IEEE,Hooghly,India.2015:1-6[17]ChoureyV,KalaP.ClusterHeadElectionApproachbasedonWeightedClusteringAlgorithmforMANET[J].InternationalJournalofComputerApplications,2015,117(19):12-17.[18]WestDB.IntroductiontoGraphTheory.Thesecondedition[M].Beijing:ChinaMachinePress,2006.395(DOUGLASB.WEST(美).图论导引.第2版[M].北京：机械工业出版社,2006.)[19]KushnerHJ.ApproximationandWeakConvergenceMethodsforRandomProcesseswithApplicationstoStochasticSystemsTheory.MITPress,CambridgeMA[J].1984,80(392).[20]TorkestaniJA,MeybodiMR.Mobility-basedmulticastroutingalgorithmforwirelessmobileAd-hocnetworks:Alearningautomataapproach[J].ComputerCommunications,2010,33(6):721-735.400[21]JianW,YangL,ZhaoY.ResearchofWirelessSensorNetworksCross-layerEnergyOptimizationBasedonLinkQuality[C]//InternationalConferenceonMeasuringTechnology&MechatronicsAutomation(ICMTMA).IEEE,Shanghai,China.2011:1092-1094.[22]CorreiaLHA,MacedoDF,SantosALD,etal.Transmissionpowercontroltechniquesforwirelesssensornetworks[J].ComputerNetworks,2007,51(17):4765-4779.405[23]PastorsatorrasR,VázquezA,VespignaniA.DynamicalandCorrelationPropertiesoftheInternet[J].PhysicalReviewLetters,2002,87(25):527-537.[24]SuH,WangXF.PinningControlofComplexNetworkedSystems:Synchronization,ConsensusandFlockingofNetworkedSystemsviaPinning[M]//BerlinHeidelberg,Springerpress,2013.[25]AndersonJE.ReviewofStochasticmodelsforlearning[J].MathematicalGazette,1955,39(6):464a.410[25]MaChun-Guang,YaoJian-Sheng.NS-3foundationandapplication[M].Beijing:Posts&TelecomPress,2014.(马春光,姚建盛.NS-3网络模拟器基础与应用[M].北京：人民邮电出版社,2014.)[26]PoojaKharga,DrRakeshJha.AComparativePerformanceAnalysisofRoutingProtocolsinMANETusingNS3Simulator[J].WirelessCommunication,2015,7(4):62-68.-14-'