受限网络中基于历史异步路由及中继数量研究

1受限网络中基于转发历史异步路由及中继数量研究陈辉1樊秀梅1单志广2（1北京理工大学计算机科学技术学院智能信息技术北京市重点实验室，北京，100081）（2国家信息中心信息化研究部，北京，100045）摘要：由于节点的移动性、稀疏链路和节点的不可靠，受限网络节点之间在大部分时间处于断开状态，现有的同步路由方法不能适用这种实际情况，所以必须从异步角度来考虑这类网络环境下的路由问题。本文完全从异步的角度思考无线自组织网中的路由问题，利用分组转发的历史信息智能做出路由决策，并研究中继节点数量对性能的影响，以减少由于复制大量分组而产生的网络流量。本文详细介绍了我们提出的方法，并通过仿真实验和一些相关算法进行比较，分析算法性能。关键词：路由受限网络机会通信容迟网络中图分类号:TP393文献标识码:A文章编号:ForwardedHistory-basedAsynchronousRoutingforChallengedNetworksandResearchoftheNumberofRelaysCHENHui1FANXiumei1SHANZhiguang2（1BeijingLaboratoryofIntelligentInformationTechnology,SchoolofComputerScience,BeijingInstituteofTechnology,Beijing100081PRC）（2InstituteofInformationResearch,StateInformationCenter,Beijing100045）Abstract:Forthereasonofthemobility，fallibilityofnodes,andthesparsityofLinks,mostofthetimelinksinchallengedNetworksaredisconnected.Traditionalsynchronousroutingmethodsareunsuitableforthiscircumstance,thusweshouldconsidertheroutingproblemofchallengednetworksinanasynchronousway.Inthisarticle,weproposeatotallyasynchronousroutingalgorithm,whichusestheforwardedhistoryofthemessagestomakeroutingdecision.Thismethodcoulddecreasenetworktrafficcausedbymessageflooding.Inaddition,westudyoftheinfluenceofthenumberofrelaysontheperformance.Thispaperelaboratesourmethodandanalysestheperformanceofourmethodbycomparingthesimulationresultwithsomeothermethods.Keywords:routing，challengednetworks，contact，Delaytolerantnetwork本文受到国家自然科学基金（No.90604012）、国家高技术研究发展计划（863计划）（No.2007AA01Z220）和新世纪优秀人才计划（NCET-07-0074）资助。陈辉，研究生，研究领域为无线网络、容迟网络的路由技术。[e-mail]单志广，博士，研究员，研究领域为计算机网络、Petri网理论与应用等；[e-mail]通讯作者：樊秀梅，博士，副教授。研究领域为计算机网络，无线网络，网络性能评价等。[e-mail]:1302196169821简介无线自组织网（MANET，MobileAd-hocNetwork）是一种典型的分布式网络模式，这对节点间的相互通信提出了很多挑战。针对无线自组织网的路由问题，大量算法已被提出[1～5]。为了研究问题的简单化，大多数学者的研究都基于这样的假设：只有在相互连接的同一云图中的节点间的通信才是有意义的，即通信都是同步的。然而在实际的应用中这种假设被越来越多的打破，在实际中可能需要在不同的连接云图中通信，或者是某一地区由于某些原因，比如节点比较稀疏,节点能量管理或是节点移动比较频繁，使网络中很难维持稳定的网络拓扑结构。此外，在目前的一类越来越重要的所谓“受限网络（Challengednetwork）[6]”中，由于较大的网络延时、频繁的网络断开和间歇连接使得很难维持节点持续的连通性。在以上情况下使用现有的同步路由算法很明显不能满足这些情况下的端到端通信。异步通信很自然的适用于这些部分连接的网络环境。“受限网络”的最基本要求就是在尽量小的延迟下保证分组的成功送达，本文使用基于分组转发历史来进行路由决策，并选择较好的节点作为分组的携带者的方法来满足“受限网络”的特殊性。我们通过在DTNsim2异步事件仿真平台上实现我们提出的路由算法，并和流行性算法(Epidemicalgorithm)[7]、SimpleContact算法和GlobalKnowledge算法[8]进行比较，分析算法性能。2无线自组织网络中的异步通信我们在日常生活中经常使用Internet和在可能距离很远的其他用户进行及时通信或文件传输。在这些同步通信的情况下，源节点和目标节点建立一条端到端的路径，在这条路径上发送消息分组。如果由于某些原因，如网络异常，某一个分组发送失败，源节点会重新给目标节点发送该分组。但是像在[10]中提到的环境，不同部落间的节点可能由于没有这样的端到端的路径，这样采用同步的方法就不能进行通信，提出了异步工作模式的需求。目前提出的关于无线自组织网中的异步路由算法已有一些成果[7～14]。一种最简单的方法是源节点将分组洪泛给区域中的所有节点，直到目标节点接收到该消息，这种算法被称为流行性算法（Epidemicalgorithm[7]）。虽然这种算法保证消息以最小的延迟发送给目标节点同时保证很高的发送成功率，但这种算法产生过多的网络流量，为此也可以借鉴一些改进思路[9，11，12，17]。由于无线网络中的节点没有持续的能量供给，节点的存储能量和计算能力都是有限的，特别是在用于特殊场合传感网络中，如[13]中用于监测斑马活动规律的斑马网中，带有GPS定位系统的无线传感节点被安装在斑马身上，这些节点一旦安装完毕就不能再更换电池，所以我们希望电池能用尽量长的时间。这样，因为流行性算法产生太多的网络流量而使节点处于活动的时间会大大增加，同时节点要处理更多的分组，过大的计算量同样会消耗掉很多能量。另一方面，由于网络中节点存储能量有限，如果节点接收到的分组超过了节点的缓存的范围，节点就会丢弃掉一些优先级低或时间比较久的分组，这最终影响到分组发送的成功率。所以，实际的路由算法应该是挑选部分较好节点来转发分组，以减少不必要的网络流量。现有的大量路由算法都是围绕着如何选取较好的中继节点转发分组，如何在复制较少分组的情况下仍然能达到较好的传输效果。KevinFall等人提出了几种依靠网络知识来转发分组的算法〔8〕。这些算法使用一种类似于传统网络路由协议的链接量度，每个节点都建立一个全局网络拓扑结构图，最终在这个图上运行最小路径算法来计算出一条最小路径，使用这条路径上的节点转发分组。MircoMusolesi等人提出了一种Context-AwareRouting路由算法〔11〕。这种算法里节点从利用环境信息合成传输可能性信息来进行路由决策。在同步路由时节点周期性的发送同步路由需要的潜在信息和它给其它节点传输可能性的列表。节点收3到这些消息后更新自己的路由表。对于异步路由，每一个节点都维持一个列表，这个列表中保存(目标节点，最好节点，传输可能性)这样的组。当一个节点被选为消息携带者并接收到消息后，节点把消息存入缓冲区中。这个携带消息的节点执行同样的操作，直到消息送达目标节点。此外，他们还提出了使用卡尔曼滤波(Kalmanfilter)[21]来预测节点环境的变化和优化带宽的使用。JoyGhosh等人研究在ETNZurich校园中无线用户的移动性轨迹来验证他们在[18，19]中提出的社会性轨迹〔12〕，即移动节点经常访问一些重要地方(称作“网络中心”)，这些地方形成节点的一个“网络中心”列表并且通过混合贝努利分布把这些“网络中心”列表形成簇。簇使用“网络中心”列表和与其相关联的访问可能性，并利用这些簇作为“移动轮廓”，使用这些轮廓为移动节点提供有效的路由决策。KevinFall等人提出了容迟网络(Delaytolerantnetwork)体系结构〔1〕来处理不同“受限网络”类型间的节点的通信问题。同时，基于文献[8]的思想他们提出了几种需要网络知识的路由算法，这些算法在节点间定义一种量度，这样节点和节点间的通信机会形成一个加权图，然后利用最小路径算法寻找一条较好的路径来转发消息。EvanP.C.Jones等人对该算法进行了改进[20]。WangYong等人提出基于擦除码（Erasure-Coding）的消息转发算法来提高简单的消息复制算法〔21〕。在基于擦除码的算法中，首先在源节点对消息进行编码产生大量的编码块，然后这些编码块平均的在前N个到了的中继间分配，让它们负责转发编码块。当有部分代码块到达终端节点即可使用它们重新恢复消息。除了有效的路由以外，这种方法也能应对比较差的通道质量或网络拥塞造成的分组丢失。这些方法从不同的角度考虑无线自组网中异步路由问题，但这些方法都在某些方面存在一定的问题。我们提出的方法可以和这些方法进行了一定的融合，最终形成一种混合的路由方法，这种方法需要较少的网络知识、复制较少的消息、选择合适的中继点及中继点数量，并且能考虑到网络中大部分影响路由的因素。3基于转发历史的路由我们提出一种基于转发历史的智能路由算法（RoutingalgorithmbasedonTransferHistory，简称为FH），该算法的目标是让节点能够智能的做出路由决策，选择一些将同类消息成功送达目标节点成功率比较高的节点作为中继点来转发分组。同时FH算法使用尽量少的网络知识，便于网络的部署和扩展。FH算法用来做出路由决策的信息是基于对以往消息转发历史的统计来得到的，在算法运行初期和流行性算法类似，在这一阶段节点建立转发信息表，一旦转发信息表建立成功就开始选取部分节点而不是所有节点来转发消息。3.1系统模型间歇性断开的网络通常被建模成一系列的移动性节点，每个节点可以搜索通信范围内的其它节点并建立连接，节点具有一定的消息缓存能力和有限的带宽。当两个节点进入彼此的通信范围后，建立连接并相互发送分组消息。在传输中，发送方给接收方发送一个分组后并不将自身的分组拷贝删除。节点可以直接或通过其它中间节点将分组发送给目标节点。假设目标节点有足够的空间存储接收的消息，则只有传输中的分组受有限存储空间的限制。间歇性断开网络中节点之间的通信机会持续的时间远小于节点间断开的时间。我们的研究实验基于图1所示的模型，模型是一个有向图结构，图中的节点表示网络节点，图中的边表示节点间所拥有的通信机会（通信机会是双向的，并且按照一定的规律到来）。异步路由算法的目标就是利用这些通信机会，将尽量多的消息从源节点发送到目标节点。4图1：实验场景示例3.2研究中的一些假定PhiloJuang等人曾提出一种基于历史的路由算法〔13〕，他们统计每个节点和接收消息的基站通信机会的历史，利用这些历史信息计算一个量度值。当一个节点要发消息时，他将消息复制给那些和它有通信机会的量度值较高的一些节点，这样消息沿着一条越来越接近基站的方向传输。这是一种坡度路由的方法，等级越高的节点在基站附件活动越频繁，同时和基站的通信的机会越多。然而这种方法存在明显的“慢启动”问题[13]，特别是在大规模网络环境中。