资源描述：
《基于喷泉编码的机会网络组播路由机制研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
分类号TN929.5密级公开UDC621.39学位论文编号D-10617-308-(2016)-01042重庆邮电大学硕士学位论文中文题目基于喷泉编码的机会网络组播路由机制研究英文题目ResearchonFountainEncoding-basedMulticastRoutingMechanismsforOpportunisticNetworks学号S130101045姓名龚玲玲学位类别工学硕士学科专业信息与通信工程指导教师杨静高工完成日期2016年6月8日 重庆邮电大学硕士学位论文摘要摘要传统移动自组织网络中不存在中心节点及固定基础设施，节点通过端到端路径进行数据传输。然而，在一些实际应用环境中，节点分布稀疏、运动频繁等因素使得网络呈现间断性连接，需要消耗大量的网络资源进行路由恢复和重建。为了满足这种特殊环境下的通信需求，研究人员提出了机会网络体系架构。区别于移动自组织网络，机会网络中节点采用“存储-携带-转发”的模式，依靠节点运动带来的通信机会实现数据转发，这种灵活的通信方式促进了机会网络的发展应用。机会网络中较多的数据通信都需要以群组的形式进行，这种需求促使了机会网络中组播通信的发展。鉴于网络的间断连接特性，传统的组播路由机制很难适用于机会网络。因此，为实现机会网络中可靠的组播通信，文中提出对机会网络中的组播路由机制进行研究。首先，文中介绍了机会网络的基本概念、特点和典型应用场景，并对当前的研究热点进行了分析，重点描述了机会网络中的组播通信，深入分析了现有组播路由机制的特点并进行总结。其次，利用节点的社会关系，并结合喷泉编码的方法，文中提出了一种带有社会关系感知的机会网络组播路由机制。根据节点的运行状态感知节点间的社会关系以及节点的数据转发能力，进而对中继节点做出选择，并结合喷泉编码特性提出冗余检测算法以降低不必要的数据转发。仿真结果表明，所提出的机制能够以较低的网络开销实现较高的数据投递。再次，为了均衡节点的转发负载，文中提出了一种编码速率受控的最优匹配组播路由机制。通过连接度、服务度、扩散度三种参数综合评估节点的转发效用，并利用最优匹配算法选择中继节点，使得尽可能多的有用节点参与到组播通信中，同时通过估计组播通信容量对编码速率进行控制。仿真结果表明，所提出的机制能够均衡节点转发负载，实现较高的通信效率。最后，对论文工作进行了总结，并提出了未来工作展望。关键词：机会网络，组播路由，喷泉编码，节点关系，最优匹配I 重庆邮电大学硕士学位论文AbstractAbstractThereisnocentralnodeandfixedinfrastructureinMANETs(MobileAd-hocNetworks),wherenodestransmitdatathroughtheend-to-endpath.However,thelownodedensity,unpredictablenodemobilityandotherfactorsinpracticalapplicationsleadtotheintermittentlyconnectednetwork,whichconsumesmassivenetworkresourcestorecoverandreconstructroutes.Targetingatthecommunicationrequirementsinthisspecialenvironment,researchersproposedthearchitectureofopportunisticnetworks.DifferentfromMANETs,the“store-carry-forward”modeandcommunicationopportunitiesbetweennodesareexploitedforthedataforwardinginopportunisticnetworks.Andtheflexiblecommunicationmeansofopportunisticnetworkshavefacilitatedthedevelopmentofopportunisticnetworks.Inmanycommunicationscenarios,datahavetobetransmittedtoagroupofnodesinopportunisticnetworks,namelythemulticastcommunication.Duetotheintermittentnetworkconnectivity,traditionalmulticastroutingmechanismsarenotsuitableforopportunisticnetworks.Inordertoachievethereliablemulticastcommunicationinopportunisticnetworks,thisthesisisintendedtostudythemulticastroutingmechanismsinopportunisticnetworks.Firstly,thebasicconcepts,characteristics,typicalapplicationscenariosandcurrenthotspotsofopportunisticnetworksareintroduced.Thenthepresentationofmulticastcommunicationinopportunisticnetworksandthecharacteristicsofexistingmulticastroutingmechanismsareprovidedminutely.Finally,thesummaryisgivenattheendofthischapter.Secondly,therelationshipbetweennodesisstudiedinthisthesis,andcombinedwithfountaincodes,asocialrelation-awaremulticastroutingmechanismforopportunisticnetworksisproposed.Therelationshipbetweennodesanddataforwardingcapabilityofnodecanbelearnedfromtherunningstateofnodesforareasonablerelaynodeselection.Besides,redundancydetectionisproposedtoreducetheunnecessarydataforwardingbasedonthecharacteristicoffountaincodes.Thesimulationresultsshowthattheproposedmechanismcanachievehighdeliveryratiowithlownetworkoverhead.II 重庆邮电大学硕士学位论文AbstractNext,anoptimalmatchingmulticastroutingmechanismwithcontrolledcoderateisproposedtobalancetheloadsbetweennodes.Basedontheconnectivitydegree,servicedegreeanddiffusiondegree,theforwardingutilityofnodecanbeobtained.Andtoinvolveasmanyusefulnodesaspossibleinthemulticastcommunication,theoptimalmatchingalgorithmisutilizedtoselectrelaynodes.Furthermorethecoderatecanbecontrolledaccordingtothemulticastcommunicationcapacity.Thesimulationresultsshowthattheproposedmechanismcanachievethehighercommunicationefficiencybybalancingthenodeforwardingload.Finally,theresearchworksareconcludedandthefutureworksarepresented.Keywords:opportunisticnetworks,multicastrouting,fountaincodes,noderelationship,optimalmatchingIII 重庆邮电大学硕士学位论文目录目录第1章引言...................................................................................................................11.1机会网络介绍...................................................................................................11.1.1机会网络基本概念.................................................................................11.1.2机会网络特点.........................................................................................21.1.3机会网络应用场景.................................................................................31.2机会网络的研究热点.......................................................................................51.3选题意义及主要工作.......................................................................................81.4本文结构安排.................................................................................................10第2章机会网络中的组播路由机制.........................................................................112.1机会网络中的数据组播.................................................................................112.2机会网络中的组播路由机制.........................................................................132.2.1基于单播的组播路由机制...................................................................132.2.2基于树的组播路由机制.......................................................................132.2.3基于相遇历史的组播路由机制...........................................................152.2.4基于社会属性的组播路由机制...........................................................162.3本章小结.........................................................................................................18第3章带有社会关系感知的机会网络组播路由机制.............................................193.1研究背景.........................................................................................................193.2编码数据生成.................................................................................................203.3编码数据转发.................................................................................................213.3.1节点关系感知.......................................................................................213.3.2数据转发机制.......................................................................................223.4会话目标节点协作译码.................................................................................273.5数值分析.........................................................................................................283.5.1不同编码冗余下的网络性能...............................................................293.5.2不同会话组大小下的网络性能...........................................................30IV 重庆邮电大学硕士学位论文目录3.5.3不同缓存大小下的网络性能...............................................................333.6本章小结.........................................................................................................35第4章编码速率受控的最优匹配组播路由机制.....................................................364.1研究背景.........................................................................................................364.2转发效用估计.................................................................................................374.3中继节点匹配.................................................................................................394.4编码速率控制.................................................................................................434.5数值分析.........................................................................................................444.5.1不同会话组大小下的网络性能...........................................................454.5.2不同节点移动速度下的网络性能.......................................................474.6本章小结.........................................................................................................49第5章结束语.............................................................................................................505.1全文工作总结.................................................................................................505.2未来工作展望.................................................................................................51参考文献.......................................................................................................................52致谢...............................................................................................................................57攻读硕士学位期间从事的科研工作及取得的成果...................................................58V 重庆邮电大学硕士学位论文第1章引言第1章引言1.1机会网络介绍1.1.1机会网络基本概念近年来，随着无线通信技术的不断进步，支持短距离通信的便携式智能终端不断涌现，手机、平板电脑等个人手持终端的应用也逐渐普及。随之依靠移动终端自带的短距离无线通信接口自组织构建网络，为复杂环境下用户间通信提供支[1,2]撑的移动自组织网络(MobileAdHocNetworks,MANETs)应运而生。MANETs无需固定的网络基础设施，利用预先建立的端到端路径，通过节点运动协作转发数据，同时结合网络信息不断更新节点的路由列表以提高通信路径的有效性。这种“存储-转发”的通信模式增强了数据转发的灵活性，同时能够均衡网络负载。移动自组织网络中路由信息是数据传输的关键。而在一些实际应用场景中，通信节点移动频繁、分布稀疏且不均匀、射频关闭等致使网络拓扑结构时常变化，链路间歇性连接，网络中不存在一条稳定的端到端通信路径。这种环境中，节点路由信息的更新速度很难适应网络拓扑结构的变化，数据传输频繁失败，使得网络性能急剧下降，数据传输业务无法正常运行。为了有效解决此类问题，满足上[3]述特殊环境下的通信需求，研究人员提出了机会网络体系架构。与移动自组织网络不同，机会网络中节点以“存储-携带-转发”的方式进行数据传输，利用节点移动带来的相遇机会实现节点间的通信，无需预先在源节点与目标节点间建立一条完整的通信路径。这种方式极大地提高了数据转发的灵活性，有效地利用了网络资源。机会网络中每个节点都具有存储、携带、转发数据的功能，数据传输具体过程如图1.1所示。图中s为产生数据的源节点，d为接收数据的目标节点，n1~n3为网络中的普通节点，源节点s需要将产生的数据传输到目标节点d。在t0时刻，目标节点d不在源节点s的通信范围内，两者无法直接传输数据，而此时普通节点n1恰好在源节点s的通信范围内，因此，源节点s首先选择将数据转发给普通节点n1。普通节点n1接收并缓存数据，作为数据的中继节点携带数据继续运动。在t11 重庆邮电大学硕士学位论文第1章引言时刻，普通节点n1与n2进入彼此通信范围内，节点n1将数据转发给节点n2，节点n2接收数据并等待下一次通信机会。同理，在下一时刻节点n2将数据转发给与其相遇的普通节点n3，直至t3时刻将数据投递到了目标节点d，完成了数据传输。图中给出的两个坐标：横坐标为时间轴，纵坐标为空间轴。显然，无论是从时间域还是从空间域的角度观察，机会网络中的数据传输过程都是不连续的，节点只能通过间断的连接机会进行通信。Spacen3n1n3sn3dddn1n2ssn2n1n3n2n1n2dst0t1t2t3Time图1.1机会网络数据传输过程1.1.2机会网络特点如前所述，机会网络作为一种移动自组织网络的演进和拓展网络，主要应用于基础设施匮乏且环境相对复杂的网络环境中。因此，除了具备一些与移动自组织网络相同的特征外，机会网络中还存在区别于其他网络的特点。自组织性：网络中无固定的基础网络设施，节点通过无线通信接口与其他节点进行通信，进而自组织形成一个局部网络。无中心性：网络中每个节点既可以作为主机，又可以作为路由器，采用分布式的方式感知其他节点的状态，并独立进行数据转发决策。多跳性：机会网络中节点分布稀疏，且节点的传输范围有限，通过节点间直接投递的方式实现数据通信不再适用于当前网络状况。网络中的数据传输主要依靠节点间的相互协作进行，并采取逐“跳”的方式中继完成数据的转发。拓扑多变性：机会网络中节点移动频繁，致使网络拓扑结构动态变化，拓扑结构的不稳定性使得网络信息的实时获取十分困难，信息的准确性也很难保障。2 重庆邮电大学硕士学位论文第1章引言连接间歇性：网络中节点通信范围有限，一旦离开节点通信覆盖范围，节点间的连接将断开，数据传输将中断。只有节点再次进入通信覆盖范围内时，才会产生新的连接。传输高时延性：网络依赖节点移动带来的通信机会进行数据转发，而稀疏的节点分布使得节点间的通信机会较少，数据通常以较大的概率在中继节点处滞留以等待合适的转发机会，该过程将产生较大的时延。节点社会性：社交网络中，节点的携带者通常是人或者有集群特性的动物，因此其行为表现出一定的社会属性，节点关系也因此呈现出差异性和非对称性。1.1.3机会网络应用场景机会网络以极其灵活的方式实现数据通信，很大程度上降低了网络基础设施建设所带来的成本开销。基于这种通信优势，机会网络在多个领域中都呈现较大的应用潜力。国内外研究人员关于机会网络在实际环境中的应用研究也逐步加强，主要涉及到应急救灾、车载网络组网、野生动物追踪、个人终端设备组网等。1.应急救灾在一些突发紧急情况或者自然灾害的影响下，固有的基础网络设施很可能被损坏，无法再为现场的人员提供通信服务。这种恶劣的环境中，机会网络凭借其不需要基础网络设施的支撑，通过现场的手持终端设备或者移动设备进行组网，[4]以满足应急救灾过程中的通信需求。类似的应用还有CenWits，即一种户外跟踪系统，可应用于偏僻的山野地区检测登山者的位置信息。作为一种松散耦合系统，该系统不需要网络的持续连接，利用登山运动者携带的终端设备进行通信。通过设备配置的射频传感器可将自身的位置信息告知途中的相遇者，同时获知对方的信息，而每个终端设备通过与其对应的唯一的ID号进行标识。当两个登山者相遇时，彼此成为对方的“目击者”，一旦有登山运动者失联或者遇险，则可根据与其最近一次相遇的“目击者”的记录信息进行搜救。2.车载网络组网作为机会网络的一大应用，车载组网主要应用于监测道路交通情况以及环境状况，进而有效地预防道路拥堵，避免交通事故的产生。麻省理工学院[5](MassachusettsInstituteofTechnology,MIT)开发的CarTel系统，在每个车辆都安3 重庆邮电大学硕士学位论文第1章引言装上低功耗的传感器，同时在车流量较大的区域部署收集转发数据的固定节点。如图1.2所示，网络中的节点主要分为两类：固定部署节点和普通车辆。普通车辆以“存储-携带-转发”的方式将信息转发给其他车辆，同时依赖与其他车辆间的信息交换以获知更多的交通路况信息，及时地调整驾驶路线。当车辆运行到固定部署节点所检测范围内时，将上传运行过程中所收集到的路况信息给固定部署节点，工作人员根据部署节点所汇总到的数据对道路进行管理，并及时告知行驶车辆道路的情况，以降低车辆的拥堵，避免交通状况的恶化。Transmit图1.2车载网络系统CarTel3.野生动物追踪野生动物群体活动的范围较广，所在的地理位置相对偏僻，通信基础设施的建设十分困难且成本较大，因此，难以应用传统的组网方式来监测动物群体的生活习性。鉴于动物监测过程中对数据的实时性要求不高，收集数据的过程相对持[6]久，研究人员提出将机会网络应用于该领域。ZebraNet追踪系统则是一种典型应用范例，由普林斯顿大学于2002年设计，用于追中非洲斑马迁徙数据。该系统在斑马脖子上安置了小功率传感器以收集数据，并通过不同斑马群体的移动进行数据交换。研究人员定期进入监测区域，对监测到的数据进行收集整理，以获知斑马群体迁徙行为的规律。4.个人终端设备组网物联网、移动互联网相关技术的发展推进了各种移动智能终端的普及应用，而用户对个人泛在化通信的需求也越来越高。作为泛在网络的重要支撑，移动自4 重庆邮电大学硕士学位论文第1章引言组织网络的研究也随之深入。无处不在的智能终端为个人移动终端组网的发展提供了基础，尤其在人口相对密集的地方，移动终端的密度较大，可通过终端节点移动带来的相遇机会进行通信。这种方式能够为用户提供相对便捷的数据通信服务，而不需要通信服务提供商的支持，极大地减少了数据传输的成本。PSN(Pocket[7]SwitchedNetwork)即为一种个人移动终端组网，由Intel研究院与剑桥大学共同提出，该网络主要通过智能设备的移动进行数据转发，为用户提供快速的低成本的信息服务。1.2机会网络的研究热点区别于传统的移动自组织网络，机会网络的特殊性使得传统网络上的研究成果无法直接应用于其网络架构中，因此，研究人员从多个角度对机会网络展开了研究。随着研究的不断深入，机会网络相关的研究成果也在不断扩展。而近年来关于机会网络的研究工作主要集中在几个方面，主要包括缓存管理机制、隐私保护机制、信任管理机制以及数据转发机制等。1.缓存管理机制机会网络中节点间歇性连接，通信时间有限，缓存中所存储的数据很难通过一次相遇全部转发，部分数据可能长时间滞留在节点缓存中。而为了增大数据成功投递的概率，大部分的数据转发机制采用多路径并行传输的方式，也就意味着网络中的冗余副本将会增多，节点的缓存资源将快速被占用。当数据得不到及时转发时，所滞留的数据将越积越多，最终导致节点的缓存空间被消耗殆尽，而无法接收新的数据。显然，如何对缓存中的数据进行管理是必须考虑的问题。对节点缓存进行管理的传统方法包括：Drop-tail、Drop-front、Drop-random、[8]Drop-oldest。四种机制分别采用优先删除队列的尾部数据，优先删除队列的头部数据，随机删除以及删除最老数据的方式对节点缓存进行管理。这些机制虽然都为机会网络所使用，但没有考虑到机会网络本身的特性，在性能上很难有较大的提升。针对机会网络的特性，研究人员提出了新的缓存管理策略，通过对节点连接状态、数据转发情况以及节点的社会属性等网络参数进行动态估计，并在此基础上对缓存进行管理，删除部分效用较低的数据，预留节点缓存空间以接收新的数5 重庆邮电大学硕士学位论文第1章引言据。文献[9]提出利用节点相似性确定数据转发的优先级，相遇节点与目标节点的相似度越高，节点赋予该数据的优先级则越高。文献[10]、[11]结合数据的扩散度对缓存中的数据进行管理，节点相遇时通过交互各自缓存的数据以统计携带指定数据的节点数，当发现携带指定数据的节点数超过一定阈值时，表明数据在网络中扩散度已较大，本地节点将删除自身缓存的数据副本，以清除缓存接收其他数据。文献[12]提出对数据进行分类，分别存储到缓存中高、中、低等级的三个列队中，能够直接投递的数据存储在最高等级的列队，根据预测机制估算出投递率较高的数据存储于中等级列队中，剩余的数据则存放于最低等级的列队中。当节点缓存不足时，优先删除等级较低的数据。2.隐私保护机制机会网络中节点通过相互协作实现数据传输，并且利用无线信道传输数据，这种共享特性无法保障网络中用户数据的安全性和隐私性。用户数据的泄露可能致使网络中更多的攻击者有机可乘，使得用户的权益进一步受到侵害。数据安全作为通信服务质量的一种重要衡量标准，是提高机会网络实用性的关键。显然，设计有效的隐私保护机制提高数据传输的安全性是必须研究的方向。传统的网络中，采用秘钥管理的方式以提高网络通信安全，机会网络的特殊性使得传统的方式难以继续使用：首先，节点高移动特性，无法保障端到端路径，使得源节点与目标节点的安全信息交互困难；同时，网络中缺乏中心节点与各节点之间的可信任连接，难以提供秘钥查询服务；其次，机会网络中传输时延较大，数据需经多个中继节点传输才能到达目标节点，要求返回时间短且需可靠路径支撑的传统安全机制难以适用；此外，机会网络中的数据通信需要节点协助完成，数据势必会传输到协助中继节点或者为其他节点监听，因此，有必要针对机会网络的特性设计可靠的隐私保护机制。机会网络研究小组(DTNResearchGroup)专门针对数据的安全性问题提出了[13]束安全协议规范(BundleSecurityProtocolSpecification,BSPS)，其中规定了四种用于扩展束的安全服务信息，分别是：束鉴权字段、有效负荷完整性字段、拓展部分安全字段以及有效负荷机密性字段。尽管上述协议规范能够提供数据的安全保护，但其建立在网络中所有节点公钥可获知的基础上。因此，如何在机会网络的特殊环境下分配和管理公钥成为了当前研究所要解决的问题。6 重庆邮电大学硕士学位论文第1章引言3.信任管理机制较多的数据转发机制都需建立在节点自愿协作的基础上，然而，机会网络中节点缓存、能量等资源受限，且受社会属性的影响，节点可能表现出非协作行为。[14-16]显然，这对于机会网络中的数据通信具有十分恶劣的影响，并且很大程度上制约了数据的有效投递。因此，有必要对机会网络中节点转发行为进行研究。针对网络中节点的协作行为，研究人员提出了一系列的信任管理机制以提高数据转发的可靠性。根据节点的信任评估方式现有机制主要分为三类：第一类是[17]基于虚拟货币的信任管理机制，数据的转发视为有偿行为，并以虚拟货币的方式进行衡量。该机制需要信任中心或者其他硬件施设的支撑，以管理虚拟货币以及节点的声誉值，这种方式仅适用于存在摆渡节点或者固定设施的网络。第二类[18]是基于博弈论的信任管理机制，利用博弈理论模型最大化节点利益，同时激励网络中的自私节点参与协作转发。该机制对于自私节点有一定的激励作用，但对[19,20]于恶意节点则无效。最后一类是基于声誉值的信任管理机制，网络中节点被赋予声誉值，当节点积极协作转发数据时声誉值将会提高，而当节点自私不接收或者产生恶意行为时，其声誉值将迅速下降。声誉值过低的节点，其自身的数据将得不到转发；声誉值较高的节点，在其为网络中其他节点转发数据的同时，自身的数据也会被积极转发。这种方式能够较好地激励节点参与到数据转发中，并且不需要使用集中认证的方式管理节点的行为，适用于机会网络的通信环境。而由于机会网络自身的特殊性，当前的信任管理机制仍不能完全解决网络中节点的非协作行为，因此，在信任管理机制方面的研究还需有进一步的提高。4.数据转发机制机会网络中节点分布稀疏，网络拓扑结构变化频繁，数据转发完全依赖于节点运动带来的相遇机会进行。显然，如何充分利用节点运动产生的通信机会是实现数据转发的关键。由于机会网络中采用“存储-携带-转发”的通信模式传输数据，如何选择存储携带数据的节点是实现高效数据转发的关键。由此可见，机会网络中数据转发的核心问题即是如何有效地选择下一跳节点，实现高效的数据传输。机会网络相对复杂的网络环境为数据转发机制的设计带来较大的挑战，而国内外研究人员根据机会网络的特性，针对不同的应用场景和通信需求，提出了多种不同的解决方案，并取得了一定的理论研究成果。7 重庆邮电大学硕士学位论文第1章引言首先，按照数据转发过程中是否生成数据副本，可将现有的数据转发机制划分为单副本策略和多副本策略。单副本的数据传输方式在整个通信过程中仅存在一个数据副本，即节点将数据转发给下一跳节点后，自身缓存中将不再保存该数[21]据，较经典的就是直接传输机制(DirectTransmission,DT)。这种数据传输的优势在于减少了网络中数据交付量，极大地降低了传输过程所产生的开销。但是这种方式的投递效率通常不高，传输时延也比较大。相比单副本的方式，多副本方式的工作原理相反，其在网络中投递的数据副本较多，最为典型的就是基于洪泛的[22]数据转发机制Epidemic。该方式能够有效地提高数据成功投递的概率，不足之处则在于网络中的资源消耗将会增大。综合两者的优势，如何均衡网络中的数据副本数与资源消耗，设计高效的多副本数据转发机制是当前的主要研究方向。其次，按照接收数据的目标节点数目，可将数据转发分为单播通信和组播通信。单播通信，即为点到点的数据通信，源节点仅将数据转发给一个目标节点。对于这类型的数据转发，研究人员已经提出了不少的机制解决所面临的问题。组播通信，与单播通信不同，作为一类点到多点的数据通信，源节点需将数据传输到一组目标节点，也就意味着在数据转发的过程中需兼顾多个不同的目标节点，以确保对于不同目标节点间的有效数据投递。此外，由于机会网络拓扑的多变性，目标节点在不同的通信组间变动，实际接收数据的目标节点与预期的目标节点并非完全相同，这种变化给组播通信以及数据转发机制的设计带来了很大挑战。1.3选题意义及主要工作机会网络中，诸多应用需要以群组的方式进行数据转发，源节点需将相同的数据同时转发给多个不同的目标节点。若在此种通信过程中使用单播或者广播的通信方式传输数据，将使得数据副本随着目标节点数目的增多在网络中不断扩散，进而导致有限的网络资源被快速消耗。与上述通信方式不同，组播路由机制通过建立源节点与多个目标节点之间的逻辑关系，能够以较少的转发次数实现群组通信，有效地降低数据转发过程中所消耗的网络资源。因此，有必要对机会网络中的组播路由机制进行研究以保障组播通信的正常运行。机会网络中的数据通信完全依靠节点间的协作进行，这种依赖性使得数据的传输质量受链路连接状况、节点协作程度的影响较大，因此选择合适的中继节点8 重庆邮电大学硕士学位论文第1章引言尤为重要。其次，在组播通信过程中，数据通常面临着中途丢失或者在中继节点处长时间滞留的情况，这都使得组播通信的效率大幅度下降，显然，对于缺少端到端反馈的机会网络，需提高数据传输的可靠性。此外，机会网络中的通信面临较长的传输时延，通信组成员可能在传输过程中发生变动，如何提高动态目标成员的数据接收率也是必须考虑的问题。针对上述问题，本文提出对机会网络中的组播通信进行研究，旨在设计高效的组播路由机制以实现可靠的数据投递，研究重点主要有以下几个方面：1.编码数据转发及冗余管理文中提出结合喷泉编码的方式传输数据，引入部分冗余数据以提高机会网络中组播通信的可靠性。凭借喷泉编码在组播通信中的优势，在传输途中丢失的编码数据可由其他携带相同数据的编码数据弥补，通过这种方式降低数据丢失或者数据滞留给整个通信带来的影响。然而，网络中并非所有的编码数据都具有较高效用，因此提出结合网络中数据转发情况对部分效用较低的编码数据进行管理。2.带有节点关系强度感知的组播路由机制机会网络中节点关系存在差异性和非对称性，而关系强度越大的节点间交互数据的可能性越大。为选择可靠的中继节点提高组播通信效率，文中综合考虑了节点间的社会关系，提出了朋友节点和普通节点的概念，并在不同类型的节点间构建不同的中继节点选择标准，以实现数据投递的同时尽可能充分利用节点间的通信机会。3.编码速率动态控制网络中引入喷泉编码以增强数据传输的可靠性，原始数据以编码数据的形式注入网络并进行转发。而编码数据的生成速率直接影响着整个网络的运行效率：编码速率太大易导致编码数据的堆积，致使网络拥塞；编码速率太小可能使得有效的通信机会没有数据传输，信道利用率降低。因此，文中提出对组播通信容量进行估计，以此为标准动态调整编码数据的生成速率。4.基于最优匹配的中继节点选择机会网络通过节点移动进行数据转发，对于部分活跃在网络中的节点，通常被选作为中继节点的频率较高，转发负载较大，过于饱和的工作状态将快速消耗此类节点的能量、缓存等资源，使得网络的连通度进一步下降，影响其他节点的9 重庆邮电大学硕士学位论文第1章引言数据转发过程。为了均衡这部分节点的转发负载，使得尽可能多的节点参与到组播通信过程中，文中提出了一种基于最优匹配的中继节点选择方法，在发挥各节点转发优势的同时优化网络的运行效率。1.4本文结构安排本文主要针对机会网络中的组播路由机制进行研究，相关内容主要分为五个章节，具体结构安排如下：第一章为引言，主要介绍机会网络的基本概念、特点以及应用场景，分析机会网络中的热点研究问题，并阐述本文的研究意义、工作重点及结构安排。第二章详细介绍机会网络中的组播通信，分析现有的机会网络组播路由机制，并阐述本文所提出研究方向的合理性。第三章提出带有社会关系感知的机会网络组播路由机制，根据节点的运行状态感知节点间的社会关系以及节点的数据转发能力，并结合喷泉编码对数据进行编码转发，最后在机会网络仿真平台上对其进行验证分析。第四章提出编码速率受控的最优匹配组播路由机制，通过节点转发行为评估节点的综合转发效用，并结合最优匹配算法对中继节点做出选择，同时通过估算组播通信容量对编码速率进行控制，最后在机会网络仿真平台上对其进行验证分析。第五章对本文的研究内容进行总结，分析当前研究工作的不足，并提出未来工作的展望。10 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制第2章机会网络中的组播路由机制2.1机会网络中的数据组播组播服务支持将数据分发给一组用户，许多潜在的机会网络应用都需要以这种群组的形式进行，并且需要高效网络运行效率的支撑。例如，灾难营救现场，有效传播受害者的相关信息，及时通知救援工作者可能遇到的潜在危险。此外，组播服务在社会网络中的运用也日渐频繁，行驶在公路上的车辆间相互告知交通路况的实时信息，移动社交网络中亲朋好友之间分享热门话题、地理位置等信息都需要将数据分发到多个不同的移动设备。显然，上述行为服务的本质都是将一类具有相似行为的人以及其携带的移动设备聚合成一个群组，并在群组内进行数据共享，而群组内的人及其携带的移动设备即为群组成员。这类应用在机会网络中具有很大的代表性，组播通信服务也由此得到了广泛的推广，如今关于这方面的研究持续不断。而作为一种群组通信，组播通信不同于单播通信，数据分发过程中接收数据的目标节点不唯一甚至不确定，主要原因在于机会网络中拓扑结构动态变化，网络频繁分裂，致使组成员关系不断变化。组播通信也不同于广播通信，分发的数据仅对群组成员有效，无论是接收数据的目标节点或是发送数据的源节点都不愿网络洪泛其不需要的数据。相比另外两者，组播通信在机会网络中的研究相对较少，而传统的组播路由机制无法直接应用于机会网络，主要原因在于：(1)机会网络中拓扑结构动态变化，在组播会话的生成时间内很难维持组播树结构的连通性；(2)网络分裂频繁易导致组播通信分支的断裂，使得数据传输中断，端到端传输时延增大；(3)传统组播算法主要建立在底层网络连接良好的基础上，对于机会网络显然很难实现。对于机会网络中的组播通信，由于数据在转发过程中所经历的时延较大，组成员可能发生变化，进而使得预期的目标节点与实际的目标节点有所不同。鉴于上述问题，研究人员对机会网络中的组播通信进行了分析，并针对机会网络的特性重新定义了三种语义模型以确定组成员关系，分别是：TM(TemporalMembership)模型，TD(TemporalDelivery)模型，CMD(CurrentMemberDelivery)模11 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制[23]型。这三种语义模型明确了接收数据的目标节点，适用于不同的机会网络场景。三种模型之间的关系如图2.1所示。TMTDCMDSemanticSemanticSemantic图2.1机会网络中的组播语义模型在TM模型中定义了成员区间，成员区间为一个预先指定的时间段，而在这个时间段内定义为组成员的节点即为预期目标节点。例如：对于一个GroupID为G，成员区间为[]tt12，的数据，其预期的目标节点包括在时间段[]tt12，内组G中的所有组成员。在TM模型中没有投递时间限制，数据在任何时刻投递都是有效的。数据的预期目标节点和实际目标节点有可能不同，实际目标节点取决于网络的运行情况以及所采用的路由算法。TD模型在TM模型的基础上对数据投递时间做出了限制，该模型在采用成员区间的基础上还定义了投递区间，投递区间指数据投递的有效时间。在满足成员区间的基础上，在投递区间内可能接收到数据的组成员节点即为预期目标节点。例如：对于一个GroupID为G，成员区间为[]tt12，，投递区间为[]tt34，的数据，其预期目标节点集ITD定义如式(2.1)所示：memberrtt(,,)12为节点r在时间段[,]tt12内是否为组成员的判决，t0表示数据的生成时间，dtr(,)0表示从数据生成至转发到节点r的最小传输时延。I{rmemberrtt(,,)trueand(,)dtrtt,rR}(2.1)TD12004CMD模型中的数据除了携带有成员区间和投递区间信息外，还包含了CMD标志信息。CMD标志设定表示在数据投递时刻，仍然是组成员节点的目标节点才是预期目标节点，同时数据须保证在投递区间内被成功投递。ICMD表示在CMD模型中预期目标节点集，一旦CMD标志被设置，ICMD中将不包括在数据投递时不是组成员的目标节点，则ICMD的定义如式(2.2)：式中tmmxadtr0,tt0,3，即表示数据投递到节点r的最短时间受源节点到节点r的传输时延和投递区间的影响。ICMD{rrITDandmemberrtt(,,)m4true}(2.2)12 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制2.2机会网络中的组播路由机制至今为止，不少研究人员对机会网络中的组播路由机制进行了研究，结合机制的工作原理分析现有的组播路由机制主要分为以下几类：(1)基于单播的组播路由机制；(2)基于树的组播路由机制；(3)基于相遇历史的组播路由机制；(4)基于社会属性的组播路由机制。对于每一类组播路由机制，研究人员提出了相关的路由算法并逐步加以改进，具体路由机制将在下文给出详细介绍。2.2.1基于单播的组播路由机制基于单播的组播路由机制是实现组播通信最简单的一类路由机制，其工作原理是通过源节点以单播的形式分别向每个目标节点发送数据从而实现组播通信服务。该类路由机制在源节点处进行数据拷贝，原始的数据副本数与目标节点数相同。许多典型的机会网络单播通信路由机制，例如Epidemic机制、Spray-and-Wait机制、PRoPHET机制在组播通信中均有所应用。EMR(EpidemicMulticastRouting)即是将Epidemic算法原理应用于机会网络中的组播通信，数据如同病毒一样在网络中传输，这种方式虽然能够实现较高的数据投递，但网络中数据交付频繁，网络资源开销较大。文献[24]在此基础上做出了改进，提出一种洪泛受控的组播路由机制，对数据的生存时间以及传输范围进行限制，同时利用分层传输机制管理通信组内部和外部的数据传输，以实现传输效率与网络资源开销的均衡。显然，生存时间的设置很关键，其值越大数据冗余越多，其值越小数据被丢弃的越多。文献[25]对Epidemic算法应用于机会网络组播通信的适用性进行了讨论，研究了反熵会话、会话组大小以及数据转发策略等关键因素对投递效率的影响，并提出了一种降低节点缓存占用率的新机制。2.2.2基于树的组播路由机制基于树的路由机制在组播通信中的研究相对较多，文献[26]表明树形结构的应用能够较好地改善无线自组织网络中组播通信的传输开销，相关研究方法已逐步扩展到机会网络的组播通信中。首先是基于静态树的组播路由机制，源节点通过获取网络全局信息或者链路的概要信息构建到预期目标节点的最短路径树，并沿13 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制着树分支进行数据转发。显然，源节点到目标节点的路径是静态的，组播树分支的断裂易导致传输时延的增大，同时中继节点无法利用本地网络信息获取更好的数据转发路径。为改善上述问题，研究人员提出了基于动态树的组播路由机制(Dynamic[23]Tree-BasedRouting,DBTR)，并且假定源节点能够获知整个网络的完整信息或者概要链路信息。在组播会话组的生存期内，每个上游节点根据所获知的网络拓扑信息构建到目标节点的组播树，然后拷贝数据沿着组播树进行转发。上游节点向下游节点转发数据副本的同时分配接收列表，下游节点仅将数据转发给接收列表中的目标节点。通信过程中接收列表一旦被上游节点设定，下游节点不能再做调整，也就使得下游节点与非接收列表中的目标节点间的投递机会被浪费。在DBTR路由研究基础上，文献[27]提出了一种按需组播路由机制(On-demandSituation-awareMulticast,OS-Multicast)，基于本地所获取到的网络拓扑信息，中继节点以自身为源节点可重构并动态更新到所有目标节点的组播树，这种方式能够较好地获知可行链路的状态信息，充分利用中继节点与目标节点间的通信机会实现数据转发。而在机会网络环境下，节点分布稀疏，无法保证网络拓扑信息的准确获知，显然此类组播路由的创建方式在机会网络中的适用性不强。文献[28]中又提出了一种改进的动态组播树，与上文提及的树结构不同，这种组播树并非根据网络拓扑信息预先构建最短路径树，而是结合节点的活跃度选择中继节点，并且根据中继节点与目标节点的连接频率分配接收列表。如图2.2所示：aencounterbsplitdestinationsetabDestinationset{1,2,„,m}{}kthelementpartitionaaabbbContactratelevel(f1,f2,„,fm)(f1,f2,„,fm){d,d,...,d}12mDestinationset{1',2',...,k'}{(k1)',(k2)',...,m'}NNActivelevelabAfaiAfbiAai1i1kmAAababContactratedifferencevector(d1,d2,„,dm),di=fi-fi{d',d',...,d'}12m图2.2接收列表分配示意图仅当节点a的活跃度Aa与节点b的活跃度Ab满足AAba的关系，才进入接收列表的分配阶段。从节点a与节点b的连接频率差异向量(,dd12,...,dm)中查找出前k个14 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制最大的元素，节点a的接收列表将分配到这k个元素所对应的目标节点，节点b的接收列表分配剩余的mk个目标节点。通过上述方式，不断将接收列表分配到不同中继节点直到数据投递成功。为了减少数据副本的扩散，文献[29]提出了基于树的空间最小化组播路由机制，主要利用当前转发路径尽可能地寻找更多的目标节点，重复使用已经产生的数据副本。最终形成的树形结构将发生如图2.3所示的变化：每增加一个树分支表示多生成一个数据副本，显然后者产生的数据副本更少。采用这种树形结构进行数据组播，时延相对更高，但是可以减少参与组播通信的中继节点数目，也就减少了不必要的数据副本扩散。图2.3组播树结构演变图2.2.3基于相遇历史的组播路由机制机会网络中的节点运动并非无规律可循，基于相遇历史的组播路由机制主要根据节点的历史运动信息，统计出节点与目标节点的相遇情况，选择与目标节点相遇概率更高的节点作为下一跳节点转发数据。[30]EBMR(EncounterBasedMulticastRouting)机制是一种典型的根据节点相遇信息而设计的组播路由机制。该机制主要建立在PRoPHET路由基础上，通过预测节点与所有目标节点的相遇概率，选择相遇概率更高的节点作为中继节点转发数据。显然，数据转发决策主要取决于节点的本地信息以及相遇节点的信息，并且EBMR机制的性能很大程度上受相遇概率预测准确性的影响。文献[31]提出一种基于委托转发的组播路由机制，机制中通过使用[32]DF(DelegationForwarding)算法选择中继节点。中继节点的选择过程不是比较相15 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制遇节点间的转发效用，而是将相遇节点的转发效用与数据所缓存的转发效用阈值进行比较，选择效用值更大的节点转发数据，并且转发效用通过与目标节点间的联系频率进行衡量。上述组播路由机制中最大数据副本数没有限制，而文献[33]中提出根据缓存占用率以及数据在网络中的分布情况动态调整数据的限额，结合节点与其他节点的历史相遇情况对节点活跃度进行评估，如式(2.3)所示：CDi表示节点i的活跃度，j为与节点i连接的节点，WTij,表示节点i与节点j间的平均连接间隔时间。最终根据相遇节点活跃度的大小成比例地分配数据副本数。CDi1/WTij,(2.3)较多组播路由机制都侧重于对路由本身性能的研究，而没有考虑到真实网络可能存在的实际问题。文献[34]提出在投递率和缓存时间受限的情况下如何实现有效地组播通信，并提出了相关的组播路由机制，通过估计节点与目标节点的投递效用选择中继节点。2.2.4基于社会属性的组播路由机制上述组播路由机制的研究充分利用了节点的移动性进行组播通信。机会网络中移动设备的携带者通常是人或者是带有集群特性的动物，在这样的个体之间存在一定的社会特征，这种特征在单播通信中已得到广泛应用，而在组播通信中也在逐渐扩展。文献[35]率先从社交网络的角度对机会网络中的组播通信进行分析，利用节点的社区性和中心性综合衡量节点的效用，提出有效的数据转发策略。该机制中，分别对单数据组播和多数据组播进行讨论：单数据组播即数据被投递到一组目标节点，提出采用节点累积连接概率(CumulativeContactProbability,CCP)衡量节点的中心性，并作为选择中继节点的标准，节点累积连接概率计算方式如式(2.4)所示：N1ijTCei1(2.4)N1j1,ji其中N表示网络中的节点数目，ij是节点N和节点N的连接概率，1-ijT表示在ije时间T内节点Ni和节点Nj的相遇概率，Ci则表示在时间T内网络中的任意一个16 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制节点与Ni相遇的期望概率。同时文献中给出了实测模型下的仿真结果，较好地说明了选择节点累积连接概率衡量节点转发能力的有效性。多数据组播中，数据被投递到多组不同的目标节点，数据交付量较大，而机会网络中节点缓存有限，中继节点需有选择地接收并转发数据。文献中提出了目标意识的概念，即节点将数据转发到不同目标节点的预期投递概率，在相同情况下，中继节点优先缓存并转发投递概率较大的数据。鉴于难以获取全局信息，文中提出了基于社区划分的数据转发方式，网络中每个节点至少属于一个社区，而节点仅需存储相同社区的邻居节点信息以构建到目标节点的数据转发路径。文献[36]则从节点相似性和节点中心性等比较稳定的社会特征入手，定义了节点相似性以及中心性差异度，通过评估节点间的差异度，选择差异度较大的节点转发数据，利用增大数据扩散度的方式增大投递到会话组中的所有目标节点的可能性。考虑到越近的节点连接信息参考价值越大，文献[37]结合时间因素对节点相似性和中心性的差异度重新定义，提出了改进后的组播通信方式。[38]基于社交网络的同质性，朋友之间的特性通常是相似的，联系也相对频繁。由此文献[39]中提出了一种新的概念——目标云，即表示与目标节点接触频率高于设定阈值的所有节点的集合，并提出了一种基于云的组播路由机制。该机制中数据转发过程主要分为两个阶段：云外部和云内部。如图2.3所示：云外部，数据携带节点将根据所设定的转发标准选择合适的节点转发数据，并且利用反馈控制机制不断更新转发标准；云内部，由于节点与目标节点联系比较紧密，数据携带节点可通过直接投递的方式将数据转发给目标节点。云外部N1云内部11N2R2CloudC1R1D11SN41N3N21D2CloudC2NR4R32N32N2图2.3基于目标云的组播示意图17 重庆邮电大学硕士学位论文第2章机会网络中的组播路由机制2.3本章小结本章首先介绍了机会网络中组播通信技术的发展情况以及应用领域，并与单播通信、广播通信进行对比，说明了研究组播通信的必要性。同时介绍了机会网络中组播通信的三种语义模型，然后根据组播路由机制的侧重点对现有的组播路由机制进行了分类介绍。通过对现有组播路由机制的分析总结，不难发现，基于历史信息的组播路由机制以及基于社会属性的组播路由机制是近年的研究热点。结合这两方面的知识，本文对机会网络中的组播路由机制提出了新的研究，具体内容见第三章、第四章。18 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制第3章带有社会关系感知的机会网络组播路由机制3.1研究背景针对机会网络的特性，研究人员从不同的角度提出了相应的组播路由机制。文献[40]提出了一种按需组播路由机制，中继节点利用所获取的可用链路信息不断重构到达会话目标节点的组播树，并充分利用节点与会话目标节点直接通信的机会转发数据。显然，准确地获知链路状态、网络拓扑等信息是保障其有效转发数据的前提，而对于分布式运行的机会网络来说，上述全局状态信息难以获取。文[42]献[41]提出将PRoPHET路由机制应用于组播通信中，源节点并行传输数据副本到每个会话目标节点以实现数据组播，数据副本效用低且扩散速度快，易导致网络资源过快消耗。针对机会网络的社会特征，文献[35]充分利用节点之间的社会关系设计了相应的组播路由机制，单数据组播时主要基于节点的累积连接概率，满足一定性能要求的情况下选择最少的中继节点将数据转发给所有会话目标节点；多数据组播时，在社区划分的基础上，选择合适的中继节点将数据转发到处于不同社区的会话目标节点。通过衡量节点活跃度，文献[33]为组播过程中的副本数量设计了限额，并根据节点缓存占用率动态调整限额值大小。所提出的机制有效控制了数据副本扩散，然而，其数据转发过程中目标不明确，中继节点选择较随意，易导致冗余转发的出现。文献[34]提出了缓存时间受限的组播路由机制，采用节点在最大缓存期限内将数据投递到会话目标节点的概率作为节点效用值，并以此为依据选择中继节点。上述机制主要针对路由性能及网络开销做出改进，而这些组播路由机制有效工作的前提须保证数据在网络中可靠传输。机会网络的动态性易导致数据丢失从而影响数据成功投递率。因此，如何增强数据的可靠传输也是组播通信亟待解决的问题。现有的研究主要通过两类方法保障数据的可靠传输：一类方法是使用反馈重传机制，机会网络间断连接，反馈信息可能经历较大时延甚至无法到达源节点，且易引起反馈风暴。另一类方法则是增加数据副本，而不同会话目标节点成功接收到的数据有所差异，不加区分地增加数据副本具有一定的盲目性。显然，上述[43]方法难以适应机会网络组播通信。喷泉码(Fountaincodes)，作为一种新的编码技19 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制术，其能够实现大规模数据传输和可靠的组播/广播等业务。该编码方式无需反馈重传便可提高数据传输的可靠性，支持中断传输、异步接入服务等特点能够较好地为动态特征明显的机会网络组播通信所应用。综上分析，本章在数据组播过程中引入了喷泉编码，并结合机会网络中节点的社会属性进行数据转发，提出了一种带有社会关系感知的机会网络组播路由机制(Socialrelation-awaremulticastroutingmechanismforopportunisticnetworks，SRMR)。通过对原始数据进行编码，并综合相遇节点与会话目标节点的关系以及根据相遇历史信息所估算的相遇节点的数据转发能力，确定编码数据转发的必要性，同时对接收到的编码数据进行冗余检测，删除缓存中冗余率较高且度数较大的编码数据，以减少不必要的数据转发。3.2编码数据生成[44]LT(LubyTransform)码作为一种典型的喷泉码，能够生成任意多的编码数据，编码过程如图3.1所示，图中x表示原始数据，e表示编码数据。源节点根据给定的编码度分布函数获取编码数据的度数d，随机选择d个原始数据x进行异或，由此生成编码数据e，并在编码数据e的数据包头中增加d个原始数据参与编码的信息。重复上述过程可生成新的编码数据。x1x2x3x4x5x6x7x8„d=23321353++++++++„e1e2e3e4e5e6e7e8„图3.1LT编码示意图结合上述编码过程可知，每个原始数据融合到不同的编码数据进行组播。会话目标节点则根据译码规则对接收到的编码数据尝试译码，传输过程中丢失的数据可由其他含有相同数据的编码数据弥补，会话目标节点可通过感知原始数据的译码程度灵活地确定编码数据的接收量。各个会话目标节点并行接收编码数据，相互不受干扰，当接收到的编码数据足以译码出所有原始数据时，则无需再接收20 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制新的编码数据，否则继续接收新的编码数据直至数据译码成功。上述过程实现了各个会话目标节点自适应控制编码数据的接收量。同时方便了异步加入会话组的会话目标节点接收数据，避免了会话目标节点因为加入会话组的时间较晚而错过对部分数据的接收。而LT码存在多种不同的度分布，目前公认性能较好的是理想孤波分布(Ideal[45]Solitondistribution)和鲁棒孤波分布(RobustSolitondistribution)。鲁棒孤波分布由理想孤波分布修正得到，适用于不同规模的数据传输，并且相关文献研究表明使用这种度分布函数，三分之二左右的编码数据的度数小于等于3，度数大于3的编[46]码数据相对较少，因而平均度值较小，运算量相对较低。因此，本章采用鲁棒孤波分布作为编码度分布函数。3.3编码数据转发机会网络具有“大世界，小世界”特性，节点呈现出较强的社会属性，并以[47]自组织的方式构成不同大小的社会群体，群体内部活动相对频繁。可见，节点间的社会关系存在一定的差异，将这种差异特性融入到编码数据的转发过程中有利于提高组播路由机制的有效性。从逻辑关系角度看，根据节点关系的强度可将网络中的节点划分为朋友节点和普通节点。组播通信过程中，两类节点均有存储、携带、转发的功能，而相比普通节点，朋友节点间联系相对频繁，直接交互数据的概率较高。由于节点随机移动，节点关系强度呈现出动态特性，准确地感知节点间的关系是实现高效投递的前提。3.3.1节点关系感知机会网络中影响节点关系强度的因素较多，难以通过单一的参数准确描述节点间的关系。因此，本章综合了节点相遇次数和节点相遇持续时间长度以衡量节点间的关系强度。其中，节点间的相遇次数表示节点间相遇频繁度，显然在给定时间内节点相遇次数越多表明节点间建立连接的机会也越多；节点相遇持续时间长度体现节点间交互数据的能力，用以衡量节点相遇过程的有效性，显然相遇持续时间越长表明节点间转发数据的可能性越大，并且能够转发的数据也越多。可21 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制见，采用上述两种网络参数，分别从节点相遇的数量和质量两方面综合评估节点间的连接，以准确衡量节点间的关系强度。由于相隔时间越近的相遇情况越能反映节点当前时刻的状态，因此，为了准确评估节点间的关系，本章设定了长度为TW的滑动时间窗口，该时间段内的历史相遇记录为有效信息。节点i可根据本地缓存的历史相遇记录信息计算出与其他节点的平均相遇持续时间长度C，计算方式如式(3.1)所示：iKij,nt()(Tijkk'(,)Tij(,))1k1(3.1)Cint()j1Kij,式中，nt()表示在时间窗口内与节点i相遇过的节点的总数，Kij,表示在时间窗口内节点i与节点j相遇的总次数，Tijk'(,)表示第k次连接断开的时间，Tijk(,)表示第k次连接开始的时间。节点i与其他节点在时间窗口内的平均相遇次数如式(3.2)所示：nt()Kij,j1(3.2)Kint()根据上述朋友节点的特性，对于任意节点i，其与朋友节点的关系比较密切，在给定时间内，节点i与其朋友节点间的相遇持续时间长度将大于历史相遇持续时间长度均值，相遇次数将大于历史相遇次数均值。满足式(3.3)中的关系时，则表明节点j与节点i联系比较频繁，为节点i的朋友节点；否则为普通节点。111(3.3)ee(Cij,,Ci)(KijKi)综上所述，节点根据本地缓存的历史记录信息从相遇持续时间长度和相遇次数两个角度衡量节点间的关系强度，进而将相遇节点划分至朋友节点和普通节点集合。同时采用滑动时间窗口锁定最新相遇记录信息，以更加准确地感知节点关系，为中继节点的选择提供依据。3.3.2数据转发机制为了控制传输过程中网络资源的消耗，避免盲目选择中继节点，本章结合节点社会属性提出了一种衡量相遇节点转发能力的评估方法。如前所述，根据节点22 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制间的联系情况，可以将网络中的节点划分为会话目标节点的朋友节点和普通节点。显然，朋友节点转发效率较高。而机会网络中节点分布不均匀且节点密度较低，会话目标节点的朋友节点在网络中的分布范围有限，单纯通过朋友节点转发编码数据易造成数据传输的中断，因此普通节点的协助转发必不可少。本章针对两种类型的节点设定了不同的转发能力评估标准。1.朋友节点根据上述节点划分标准，将一类与会话目标节点直接相遇较多，成功投递编码数据可能性较大的节点定性为会话目标节点的朋友节点。然而，这些节点将编码数据投递到会话目标节点的能力参差不齐，为了进一步量化这种差异以选择更优的朋友节点转发编码数据，本章引入了节点相遇概率。相关研究对社交网络节点移动特性进行了统计分析，指出节点间的相遇过程[48]服从给定相遇强度的泊松过程，同时节点相遇间隔时间服从指数分布。因此，在时间t内，节点i与节点j的相遇概率Pij,计算方式如式(3.4)：ij,tPe1(3.4)ij,式中ij,表示节点i与节点j的相遇强度，其计算方式如式(3.5)所示：Kij,ij,Kij,(3.5)((,)TijkkT1'(,))ijk1然而，机会网络中节点缓存资源受限，为了减少编码数据在缓存中滞留的时间，提高缓存空间的利用率，本章设定每个编码数据的生存时间为TTL(TimeToLive)，且TTL3then2:whilethereareei∈S(m),m∈{1,2,3}andanyx∈eihasx∈exdo3:ex=ei^ex4:dx=dx-m5:endwhile6:ifdx==0then7:returnFALSE8:elsereturnTRUE9:elseifdx==3then10:ifthereareei∈S(3),ej∈S(2)andex==ei^ejorthereareei,ej∈S(2),ek∈S(1)andex==ei^ej^ekorthereareei∈S(1),ej∈S(2)andex==ei^ejorthereareei,ej,ek∈S(1)andex==ei^ej^ekthen11:returnFALSE12:elsereturnTRUE13:elseifdx==2then14:ifthereareei∈S(1)andei^ex∈S(1)orthereareei∈S(1),ej∈S(2)andex==ei^ejorthereareei,ej∈S(2)andex==ei^ejthen15:returnFALSE16:elsereturnTRUE17:else18:ifthereareei∈S(1),ej∈S(2)andex==ei^ejthen19:returnFALSE20:elsereturnTRUE网络中任意一个中继节点均携带有发往不同会话目标节点的编码数据，上述冗余检测是针对发往相同会话目标节点的编码数据进行的，节点能够结合本地缓存的编码数据情况检测出部分冗余度较高的编码数据，控制此类数据的转发，以提高网络资源的利用率。3.4会话目标节点协作译码组播通信过程中，相同时刻相同会话组中的会话目标节点接收到的编码数据及数目有所差异。而相同会话组的会话目标节点所要接收的数据相同，如果相同会话组的会话目标节点所接收到的编码数据聚合在一起，将能够增大整个会话组的数据接收率及完全译码的概率。根据这种思想，本章提出了会话目标节点间协作译码数据，实现所接收到的数据共享。27 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制当相同会话组的会话目标节点相遇时，首先通过交换概要向量获取相遇节点所接收到的编码数据信息和译码出的原始数据信息，获取自己没有的数据，如式(3.9)所示：iDijDi()DiDjDj(3.9)其中Dij表示会话目标节点i缓存中含有可向会话目标节点j传输的数据的集合，Di、Dj分别表示会话目标节点i和j缓存中所有数据的集合，这里的数据包括编i码数据以及原始数据，Dj表示会话目标节点i缓存中能够被会话目标节点j缓存中的原始数据直接异或得到的编码数据。由于节点连接持续时间有限，即传输容量受限，为了充分利用有限的传输资源，在会话目标节点通信时，有必要设定数据的转发优先级。原始数据不仅能够增大会话目标节点的数据接收率，同时能够促进会话目标节点译码出其他原始数据。其次，度数越小的编码数据，其译码复杂度低且译码效率较高。结合上述分析，会话目标节点i将根据度数递增的顺序向会话目标节点j传输Dij中的数据，其中原始数据视为度数为1的编码数据，并优先传输。由此，通过会话目标节点间的直接交互机会尽可能多的传输接收到的原始数据和编码数据，实现会话目标节点所存储数据的共享，增大数据传输效率。3.5数值分析[49]本章采用机会网络仿真平台(OpportunisticNetworkEnvironment,ONE)对提出机制的性能进行验证，所采用的测试环境包括模拟器自带的基于地图的移动模型以及基于Infocom06实测数据的实测移动模型，前者模型中默认的地图为赫尔辛基市中心的地图数据，后者实测数据来自于CRAWDAD(aCommunityResourceforArchivingWirelessDataAtDartmouth)公开公布的实验数据，Infocom06实测数据收集于巴塞罗那Infocom06会议期间由78名志愿者携带移动设备记录完成，移动设备采用Bluetooth2.1+EDR接口，具有250kBps的传输带宽及10m的传输距离。具体仿真参数如表3.3所示。提出的对比机制包括基于Epidemic的组播路由机制、基于限额副本的组播路[31]由机制QBMR以及基于委托转发的组播路由机制DM。对比的性能指标包括数28 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制据投递率、投递开销、传输时延。其中数据成功投递率体现了组播路由机制将数据可靠转发到所有会话目标节点的能力，计算方式为：所有会话目标节点成功接收到的数据总数/（源节点产生的数据数会话组中会话目标节点的个数）；投递开销表示成功投递一个数据平均所需的数据转发次数，计算方式为：（数据转发次数-会话目标节点成功接收的数据数）/会话目标节点成功接收的数据数；传输时延表示数据从生成到投递成功所经历的时间。表3.3仿真参数设置参数数值仿真时间/h12仿真区域/m×m4500×3400节点运动模型基于地图模型/实测模型节点个数/个126/78节点通信方式蓝牙节点缓存大小/MB[5,100]滑动时间窗口大小/h3传输范围/m10传输速度/kBps250TTL/min180数据大小/kB[200k,300k]会话组大小/个[5,30]3.5.1不同编码冗余下的网络性能采用LT码对原始数据进行编码，通常情况下，为保证原始数据的成功译码率，所接收到的编码数据数将略大于原始数据的个数，典型情况需要5%~10%的译码[50]冗余。其中译码冗余计算方式如式(3.10)所示：nk=(3.10)k其中，n表示接收到的编码数据的个数，k表示原始数据的个数。编码冗余与译码冗余计算方式相同，但n表示源节点产生的编码数据的个数。由于编码数据在传输过程中可能被丢失，同一组数据其编码冗余与译码冗余显然不同。本小节首先在不同编码冗余率下对提出机制的数据投递率进行验证，其中k为1000，每个会话组中存在10个会话目标节点，仿真结果如图3.3所示。29 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制0.900.90.850.80.800.70.750.60.70数据投递率0.65数据投递率0.50.600.4WithoutredundantdetectionWithoutredundantdetection0.55WithredundantdetectionWithredundantdetection0.30.00.10.20.30.40.50.60.70.80.90.00.10.20.30.40.50.60.70.80.9编码冗余率编码冗余率(a)基于地图模型(b)实测模型图3.3不同编码冗余率下的数据投递率图3.3中横坐标表示源节点产生的编码冗余；纵坐标表示数据的成功投递率。图中的虚线和实线分别表示在加入冗余数据检测算法前后本章所提机制数据投递的变化情况。随着编码冗余的增加，数据投递率总体呈上升趋势，由此印证了通过喷泉编码增加部分冗余数据能够提高组播数据投递的可靠性。由仿真结果可知编码冗余率在0.2前，数据投递率呈急剧上升的趋势，之后上升速度减缓。这是由于前期接收到的编码数据冗余程度较低，有助于译码，而随着译码过程的进行，后期接收到的编码数据冗余度增大，对译码的促进作用减小，会话目标节点接收新数据缓慢，数据投递率增长趋势变缓。由实线可知，加入冗余数据检测算法后，减少了部分效用较低的编码数据的转发，提高了编码数据的整体效用，上述现象得到明显改善，由此说明了本章提出的冗余数据检测算法的可行性。3.5.2不同会话组大小下的网络性能会话组大小表示会话组中会话目标节点的个数，当会话目标节点增多，网络通信任务量增大，直接影响到组播路由机制的可靠性及可扩展性。本小节主要验证固定节点缓存30M时，不同会话组大小对四种组播路由机制的影响。同时本章提出的SRMR机制编码冗余控制在0.1内，即在没有数据损失的理想情况下，会话目标节点能够通过接收到的编码数据译码出所有的原始数据，实现百分百的数据投递，显然上述情况是不可能实现的。实际仿真结果如下所述：图3.4为不同会话组大小下四种机制的数据投递情况，随着会话组中会话目标节点数的增多，不同机制的数据投递率随之上升。原因在于会话目标节点数的增30 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制多促进了携带数据的中继节点与会话目标节点相遇，数据成功投递率因此增大。而本章提出的SRMR机制结合了LT码对原始数据进行编码传输，增大了数据传输的可靠性。数值结果表明，在基于地图模型中，本章所提机制的数据投递率相比Epidemic机制提高了8.4%，相比DM机制提高了43.8%，而相比QBMR机制提高了31.8%；在实测模型下，所提机制的数据投递率相比三种机制分别提高了13.6%，42.9%，26.9%。对于Epidemic机制，网络中洪泛的非原始数据副本过多，迅速充满节点缓存空间，使得数据因为缓存溢出被丢弃，有限的缓存限制了其数据投递率；DM机制中过少的数据副本不利于数据的转发；QBMR机制数据转发过程中虽然控制了数据副本数，但中继节点的选择目标性不强，使得其转发效率较低。0.800.700.750.650.600.700.550.650.500.600.450.55数据投递率数据投递率0.400.50Epidemic0.35EpidemicDMDM0.45QBMR0.30QBMRSRMRSRMR0.400.255101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图3.4不同会话组大小下的数据投递率图3.5所示为投递开销随着会话组大小的变化情况，显然投递开销随着会话组的增大均呈现下降的趋势。主要原因在于随着会话组的增大，网络中存在的会话目标节点增多，携带数据的中继节点与会话目标节点的相遇机会增加，减少了数据的冗余转发，投递开销因此下降。数值结果表明，在基于地图模型下，本章提出的SRMR机制相比Epidemic机制投递开销降低了77.1%，相比QBMR机制降低了16.4%，而相比DM机制，仿真前期的投递开销较大，但随着会话组的增大逐渐低于DM机制；在实测模型下，本章提出的SRMR机制相比Epidemic机制和QBMR机制投递开销分别降低了74.4%，31.6%。本章所提机制通过会话目标节点协作译码接收到的数据，并且随着会话组的增大，这种协作效果得以充分体现，促进了数据投递，减少了数据转发。31 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制8070EpidemicEpidemic70DMDM60QBMRQBMR60SRMRSRMR50504040投递开销投递开销3030202010105101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图3.5不同会话组大小下的投递开销图3.6描述了四种机制在不同会话组大小下的传输时延，随着会话组的增大，四种机制的传输时延呈现下降趋势。在基于地图模型下，本章提出的SRMR机制相比Epidemic机制传输时延较高，而相比DM机制及QBMR机制具有较低的传输时延，分别下降了36.9%和17.8%；在实测模型下，本章提出的SRMR机制相比DM机制及QBMR机制传输时延分别降低了27.2%，13.0%。Epidemic机制采用洪泛转发的方式，使得数据快速被投递，传输时延较低，而随着会话目标节点的增多，与会话目标节点相遇的机会增大，这种作用更加明显。DM机制中继节点的选择阈值随着数据的转发不断提高，数据等待转发的时间逐渐加长，传输时延随之增大。而本章提出的机制结合节点社会关系选择转发能力较强的相遇节点作为中继节点，减少不必要的数据转发，传输时延因此较低。35003500EpidemicEpidemicDMDM3000QBMR3000QBMRSRMRSRMR25002500ss20002000传输时延/传输时延/15001500100010005101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图3.6不同会话组大小下的传输时延32 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制3.5.3不同缓存大小下的网络性能机会网络中节点缓存资源受限，缓存空间的大小直接关系到数据的存储量，影响数据的丢失情况，进而对整个网络的通信质量带来影响。因此在有限的存储资源下可靠转发数据是机会网络组播通信研究中不可或缺的部分。本小节主要验证在每个会话组中存在10个会话目标节点的情况下，节点缓存变化对四种机制性能的影响。不同缓存大小下四种机制的数据投递情况如图3.7所示，不种机制的投递率随着缓存容量的增大都呈上升趋势。主要原因在于随着缓存容量的增大，容纳数据的能力增强，节点携带数据的差异性增加，更有利于数据在网络中充分交换和转发，同时数据丢失的可能性降低，数据投递率因此上升。数值结果表明，在基于地图模型下，本章提出的SRMR机制相比其他机制投递率均有所提高，相比Epidemic机制提高了16.0%，相比DM机制提高了60.7%，相比QBMR机制提高了37.6%；在实测模型下，SRMR机制相比其他三种机制投递率分别提高了18.2%，75.8%，45.2%。由图可知Epidemic机制投递率受缓存影响最大，当缓存增大到80MB时，高于SRMR机制，这主要受其洪泛的转发方式的影响。相比其他两种机制，SRMR机制受缓存的影响较小，这主要因为机制中引入了LT编码，降低了数据丢失的对网络性能的影响。0.90.70.80.60.70.50.60.40.5数据投递率数据投递率0.30.4EpidemicEpidemicDM0.2DM0.3QBMRQBMRSRMRSRMR0.20.1020406080100020406080100缓存大小/MB缓存大小/MB(a)基于地图模型(b)实测模型图3.7不同缓存大小下的数据投递率如图3.8所示：四种机制在不同缓存大小下的投递开销均呈现下降的趋势，并且下降到一定程度后稳定。这主要由于缓存增大，成功投递的数据增多，无效数33 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制据转发减少，投递开销因此降低。当缓存增大到一定程度，成功投递的数据数饱和，投递开销逐渐趋于稳定。在基于地图模型下，相比Epidemic机制和QBMR机制，SRMR机制投递开销较低，分别降低了75.2%和21.5%，而相比DM机制略高；在实测模型下，SRMR机制相比Epidemic机制和QBMR机制分别降低了63.2%，10.0%。其主要原因在于SRMR机制在数据的转发过程中充分考虑了节点的社会关系，选择转发能力较强的节点进行数据转发，减少了不必要的数据扩散。7090EpidemicEpidemic80DM60DMQBMRQBMR70SRMRSRMR5060405040投递开销30投递开销3020201010020406080100020406080100缓存大小/MB缓存大小/MB(a)基于地图模型(b)实测模型图3.8不同缓存大小下的投递开销350035003000300025002500/s/s20002000传输时延传输时延15001500EpidemicEpidemic1000DM1000DMQBMRQBMRSRMRSRMR500500020406080100020406080100缓存大小/MB缓存大小/MB(a)基于地图模型(b)实测模型图3.9不同缓存大小下的传输时延图3.9描述了四种机制在不同缓存大小下的传输时延情况，从基于地图模型以及实测模型下的仿真结果来看，DM机制和QBMR机制以及本章提出的SRMR机制的传输时延随着缓存的增大呈现减小的趋势，主要原因在于缓存增大，所能容纳的数据增多，数据副本达到一定的扩散度，增大了与会话目标节点的相遇概率，34 重庆邮电大学硕士学位论文第3章带有社会关系感知的机会网络组播路由机制数据将以更快的速度投递到会话目标节点，投递时延因此减小。Epidemic机制与其他机制不同，基于洪泛的转发方式使得网络中数据量较大，所容纳的数据随缓存空间的增大而增多，然而机会网络中节点间断连接使得每次连接能够交互的数据量有限，数据因此产生滞留的时间延长，传输时延因此逐渐增大。数据结果分析可知，基于地图模型下，提出的SRMR机制相比DM机制和QBMR机制传输时延分别降低了33.6%，12.5%；实测模型下，相比之下分别降低了31.8%，6.5%。3.6本章小结为了减少数据丢失给网络带来的影响，适应会话目标节点接收状态的差异性和不确定性进行数据传输，本章引用喷泉编码于机会网络的组播通信中，提出了带有社会关系感知的机会网络组播路由机制。利用社交网络的特性对节点进行分类，准确感知不同类型的相遇节点的数据转发能力以做出中继节点选择，并结合冗余数据检测算法删除效用较低的编码数据，利用可能的传输机会优先转发效用较高的编码数据。与传统机制相比，所提出的机制能够以较低的网络开销实现较高的数据投递率，提高了网络资源的利用率。35 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制第4章编码速率受控的最优匹配组播路由机制4.1研究背景目前，研究人员针对机会网络的特性，提出了相关的组播路由机制。文献[51]最先采用节点中心性和相似性特征选择中继节点，通过最小化参与组播通信的中继节点数以达到降低资源开销的目的。文献[36]根据节点间的相似性以及中心性差异度选择中继节点，通过选择差异度较大的节点转发数据，提高数据在整个网络中的扩散度，进而增大将数据投递到所有会话目标节点的概率。虽然其在一定程度上能够提高数据投递率，但盲目地增大数据扩散度易导致不必要的数据转发，同时对于节点分布稀疏的网络适用性较低。利用节点关系强度参数选择中继节点，文献[52]结合直接投递和间接投递两种方式进行数据转发，以提高数据投递到所有会话目标节点的可能性。可见，各种机制均利用节点的社会属性实现组播数据的转发，然而，对于社会特征较为明显的节点来说，其被选择作为中继节点的概率较高，导致其所承载的数据量较大，过于饱和的工作状态将快速地消耗此类节点的能量、缓存等资源，使得网络的连通程度进一步下降，影响其他节点的数据转发过程。同时，节点运动过程中所建立的临时链路传输资源有限，单次连接无法完成此类节点中的大量数据转发，随着数据在节点缓存中的不断累积，易导致网络出现局部拥塞，最终影响整个网络性能。显然，有效利用网络资源的同时，需均衡网络中节点的负载，使得网络整体转发效益得到优化。综合上述分析，本章提出了一种编码速率受控的最优匹配组播路由机制(Anoptimalmatchingmulticastroutingmechanismwithcontrolledcoderate,CCR-OMMR)。原始数据采用喷泉码进行编码，进而，以编码数据的形式在网络中传输，并根据节点间的连接持续时间和连接次数估计组播通信容量，以最大的组播通信容量为界控制编码速率，进而控制网络负载。同时，本章设计了基于最优匹配算法的中继节点选择方法，通过衡量节点将编码数据转发到各个会话目标节点的转发效用，选择合适的邻居节点将编码数据转发到指定的会话目标节点，在有效利用节点相对于不同会话目标节点的传输优势的基础上，使得尽可能多的节36 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制点参与到组播通信的转发过程中，以达到均衡网络中节点的负载，优化网络转发效益的目的。4.2转发效用估计机会网络中的节点分布较为稀疏，数据转发过程需要多个节点以协作的方式[53,54]完成，显然，对于数据组播通信来说，中继节点的选择至关重要。为了准确感知节点转发数据的能力，本章提出了节点转发效用，即节点将编码数据直接投递或者间接投递到会话目标节点的能力。如前所述，机会网络中网络拓扑变化频繁，难以获取比较完整的全局信息来衡量节点的实际转发效用，因此，需要根据历史转发行为对节点的转发效用进行评估。为了准确、全面地评估节点转发效用，本章引入了节点连接度、服务度、以及扩散度三个参数作为评估指标。连接度主要衡量了节点与会话目标节点直接联系的频繁程度，该值越大表明节点与会话目标节点之间通信越频繁，节点将数据直接投递到该会话目标节点的机会也越多，使得节点转发效用越高；服务度表示节点为接收到的编码数据提供转发服务的能力，受节点自身转发意愿以及节点能量、缓存空间有限性的影响，节点缓存中的编码数据并非都能得到转发，可能长时间滞留也可能被丢弃。因此，通过服务度可以获知节点对编码数据的实际转发情况；扩散度表示节点将编码数据扩散到其他节点的能力，由于网络中的数据传输主要通过多个中继节点辅助的方式实现，则节点可通过其他中继节点间接地向会话目标节点传输数据，而节点将编码数据扩散得越广，编码数据被成功投递到会话目标节点的可能性也越大。可见，综合上述三个网络参量能够评估节点接收到编码数据后，通过直接或者间接的方式将编码数据转发给会话目标节点的能力，进而为中继节点的选择提供参考。连接度(ConnectivityDegree,CD)体现了节点与会话目标节点联系的频繁程度，通过在给定时间T内节点与会话目标节点直接连接的次数进行衡量，其计算方法如式(4.1)所示：C(tT)C()tidkkidCD=(4.1)idkT37 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制其中CD为节点i与会话目标节点d之间的连接度，C()tT、Ct()分别表idkkidkidk示在时刻tT、时刻t节点i与会话目标节点d联系的次数。k服务度(ServiceDegree,SD)体现了节点接收并转发编码数据的可靠程度，若节点接收的编码数据较多，但实际转发的编码数据较少甚至没有转发，则对于新接收到的编码数据不被转发的可能性较大，由此节点的服务度较低。该参数通过节点实际转发的编码数据量与接收到的编码数据量的比值进行衡量，计算方法如式(4.2)所示：Sddkk(tT)S()tSDdk=iiiddd(4.2)(Rk(tT)Rk())tLtk()iii其中SDdk为在单位时间T内，节点i相对于会话目标节点d的服务度，ikRdk()tT、Rtdk()分别表示节点i在时刻tT、时刻t接收到会话目标节点为diik的编码数据量，Sdk()tT、Stdk()分别表示节点i在时刻tT、时刻t实际发送ii会话目标节点为d的编码数据量，Ltdk()表示时刻t节点i缓存中会话目标节点为kid的编码数据量。k扩散度(DiffusionDegree,DD)表示节点将编码数据有效转发到其他节点并通过其他节点将编码数据转发给会话目标节点的能力，若邻居节点与会话目标节点的连接频繁度高于本地节点，其都有可能被选作为下一跳中继节点转发编码数据，因此，节点i与此类节点连接的次数越多，有效扩散编码数据的能力越强，扩散度的计算方法如式(4.3)所示：jDDdk=CD,(CDCD)iijidkkjd(4.3)j1其中DDidk表示节点i在单位时间T内将会话目标节点为dk的编码数据扩散到网络中的程度，j表示所有满足条件CDidCDjd的邻居节点j个数。kk节点与会话目标节点的连接度越高，直接传输编码数据的可能性越大；节点的扩散度越高，间接转发编码数据的能力越强；而服务度越大，说明节点转发编码数据的可靠性越高，编码数据被累积或滞留的概率越低。因此，基于上述参量可综合获知节点i将编码数据转发到会话目标节点d的能力，即节点i相对于会话k目标节点d的转发效用U，如式(4.4)所示：kidk38 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制ddkkU(CD0.5DDdk)e()SDiTHi(4.4)idkkidi其中THdk表示服务度阈值，其计算方式如式(4.5)所示，该数值直接体现为使得编i码数据不至于在节点缓存内累积所需的服务度大小，即上一时刻节点缓存中的编码数据在下一个单位时间内须全部被转发出去。该阈值大小随着每个节点接收和转发编码数据量的情况动态变化。Ltdk()THdk=iiddd(4.5)(Rk(tT)Rk())tLtk()iii为了提高估计结果的准确性，在评估当前时刻t节点i将编码数据转发到会话目标节点d的效用值时，综合参考了节点i的历史转发行为。时间相隔越久的历史k信息准确度越低，参考价值越小，因此，采用了指数衰减机制来处理历史参考信息，综合评估当前时刻节点i的转发效用值，如式(4.6)所示：Ut{e()tt1CD()...te()ttnCD()te()ttCD()tidkidk1idknidk0.5(e()tt1DDdk()...te()ttnDDdk()te()ttDDdk())}ti1ini{e()tt1(SDdkk()tTHd())...te()ttn(SDdk()tTHdk())te()tt(SDdk()tTHdk())}tei11iininiinn{e(ttx)CD()tCD()0.5(te(ttx)DDdk()tDDdk())}tidkkxidixixx11n()ttxdkdkdkdk{e(SDi()txTHi())txSDi()tTHi()}t(4.6)ex1t式中U表示在时刻t节点i相对于会话目标节点d的综合转发效用值，且idkkttT；CD()t、DDdk()t、SDdk()t数值主要通过观测衡量节点i在tt~xx1idkxixixxx1时间段内的转发行为获知，THdk()t则由节点i在tt~时间段内接收到的会话目ixxx1标节点为d的编码数据量以及在时刻t节点缓存内会话目标节点为d的编码数kx1k据量决定；表示衰减因子，间隔时间越近的统计数据，其参考价值越高；间隔时间越长的数据其参考价值衰减越大。4.3中继节点匹配受机会网络中节点关系差异度影响，每个节点对于同一通信组中不同会话目标节点的转发效用不同，显然选择转发效用较高的节点作为中继节点传输编码数据的效率更高。而网络中存在部分节点比较活跃，相对多个会话目标节点的转发39 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制效用都较高，这类节点经常被选作为中继节点协作转发数据，大量的编码数据流经此类节点，使得其转发负载增大，而其他节点又处于闲置状态，这种转发负荷的严重失衡将难以维持较高的网络运行效率，因此，有必要对节点的转发负载进行均衡。本章提出了一种基于最优匹配算法的中继节点选择方法，使得向不同会话目标节点传输编码数据的任务均衡到多个不同的邻居节点。根据上述节点综合转发效用的估计结果，网络中的每个节点够获知自身将编码数据转发到各个会话目标节点的能力，并且随着网络的运行不断进行更新。通过节点相遇过程进行数据交互，本地节点可获知相遇节点相对于不同会话目标节点的综合转发效用，并将相关信息存储在邻居列表中为中继节点的选择提供依据。假定本地节点i对于各个会话目标节点dd12,,...,dm的综合转发效用分别为Uid12,Uid,...,Uidm，并且其邻居列表中有li个邻居节点jj12,,...,jli。任意一个邻居节点jx，若其对于任意一个会话目标节点的综合转发效用高于本地节点i，即满足式(4.7)中的关系，则有可能被选作为下一跳转发节点。UjdUid..stx{1,2,...,},lik{1,2,...,}m(4.7)xkk根据上述标准选择所有符合条件的邻居节点jj1,,...,2jl'作为中继节点候选节i点。假定每个候选节点仅将编码数据转发给其中的一个会话目标节点，则节点i通li'过li'个候选节点传输编码数据的整体转发效用UiDUjdky,dy{,dd12,...,dm}。为k1了使得通过这些候选节点转发编码数据到各个会话目标节点的整体转发效用最大化，同时使得负责将编码数据转发到各个会话目标节点的候选节点数目得到均衡，上述问题将转化为求解式(4.8)中的最优化问题：mlmi'/maxUUiDmax(jdl)dkkkl11l..stj{,jj,...,j}dlki12'llorkk,jll12j1212ddkk12,ll{1,2,...,l'/m}12i,kk{1,2,...,}m(4.8)12上述问题等价于图论中的最优匹配求解问题，为使得整体转发效用UiD尽可能大，显然需要Ujdl的数值尽可能大，即每个候选节点尽可能地转发综合效用较大dkk40 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制的会话目标节点的编码数据，因此下文将通过最优匹配原理对上述问题进行求解，具体过程如下：(1)首先获取每个候选节点对于各个会话目标节点的综合转发效用，构建关于综合转发效用的矩阵U，如式(4.9)所示：UU...Ujd11jd12jd1mUU...UUjd21jd22jd2m(4.9)............UU...Ujdli'1jdli'2jdli'm(2)根据上述矩阵信息构建一个具有二部划分(,VV12)的加权完全二分图(U,)w，上述转发效用矩阵U则为完全二分图Ulmi',lmi',的权矩阵，对应到二部划分图中V1{,,...,jj12jli'}、V2{,dd12,...,dm}，边{,jdxy}上的权wjd(,xy)表示候选节点jx将编码数据转发到会话目标节点dy的综合转发效用值。于是，上述整体转发效用的最优化过程转换为求解完全二分图(Ulm',,)w的最优匹配问题。i当lmi'时，直接根据加权的完全二分图(Ulmi',,)w利用Kuhn-Munkres(KM)算法求解最优匹配，根据所得到的最优匹配便能获知每个候选节点最终所匹配的会话目标节点，即按照这种分工方式将编码数据转发到对应的会话目标节点所得到的整体转发效用最优。最终每个候选节点则转发对应会话目标节点的编码数据。然而，当lmi'时，根据KM算法求解出(Ulmi',,)w的最优匹配最多能为m个候选节点匹配对应的会话目标节点，剩余('lmi)个候选节点如何分配仍是问题。为此，基于KM算法的最优匹配思想，本章提出了多对一的最优匹配，以使得多个候选节点能够与同一会话目标节点相匹配。首先构建完全二分图(Ulm',,)w，并i在此基础上增加lmi'/1组虚拟的会话目标节点以构成新的完全二分图(Ulmlmii','/,)w，本章称其为虚拟完全二分图。如图4.1所示：原始的完全二分图中有li'9个候选节点jj1,,...,2j9，m4个会话目标节点dddd1,2,3,4，为了使得尽量多的候选节点根据匹配算法都能匹配到对应的会话目标节点，图中增加了一组虚拟会话目标节点dd1',2',d3',d4'，分别等效于原会话目标节点dddd1,2,3,4，且对应边上的综合转发效用值相同，即wjd(,xy)wjd(,xy')，x{1,2,....,9}，y{1,2,3,4}。41 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制j1j2j3j4j5j6j7j8j9...wjd(,)xyd1d2d3d4d1'd2'd3'd4'图4.1虚拟完全二分图根据完全二分图(Ulmlmii','/,)w，利用KM算法求解出候选节点到会话目标节点间的最优匹配关系，而最优匹配中与虚拟会话目标节点dk'相匹配的候选节点即等效为与会话目标节点dk相匹配。通过上述方式，可获知适合将编码数据转发到会d的所有候选节点，由集合12lmi'/话目标节点kJdk{jdk,jdk,...jdk}表示，即节点i将通过这些节点转发会话目标节点为dk的编码数据。(3)为了确保编码数据转发的有效性，所选择的候选节点其综合转发效用需高于本地节点，以确保编码数据能以更高的概率投递到会话目标节点。因此仅在满足式(4.10)中的条件时，候选节点才成为最终的中继节点入选节点，并作为下一跳节点转发编码数据。UjdUid,k{1,2,...,}m(4.10)xkkk同时，为了充分利用相遇节点与非匹配会话目标节点间的相遇机会，本章提出了协同转发，即利用可能的共用路径实现数据组播通信。例如网络通信过程中11节点i与节点jd相遇，根据上述匹配，候选节点jd负责转发会话目标节点为d1的111编码数据。若候选节点jd将编码数据转发到会话目标节点dkk({2,3,...,})m的效11用值满足式(4.11)中的关系，则候选节点jd将同时协助转发会话目标节点为dk的1编码数据。Jdk'1Ujd1d1kUjddlkk,k{2,3,...,}m(4.11)Jd'l1kl式中Jdk'表示负责转发会话目标节点为dk的编码数据的入选节点集，jdk表示负责将编码数据转发到会话目标节点dk的入选节点。42 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制通过上述匹配过程将会话目标节点不同的编码数据分工到不同的中继节点进行转发，当中继节点接收到编码数据后，将以相同的匹配原理选择下一跳中继节点并转发与其对应的会话目标节点的编码数据，通过这种逐跳匹配选择的方式实现编码数据的成功投递。4.4编码速率控制本章采用喷泉编码的方式对组播数据进行编码，以提高数据转发的可靠性。然而编码数据的生成速率直接影响着整个网络的运行效率：生成速率太大，源节点缓存空间占用较快，易导致局部拥塞；生成速率太小，编码数据转发较慢，可能使得有效的通信机会没有编码数据传输，网络运行效率降低。鉴于上述问题，本章提出了带有传输容量估计的编码速率控制方法，即根据组播信道的传输容量调整编码数据的生成速率。相关文献表明机会网络中节点运动呈现规律性，并且网络中节点相遇时间间[55]隔以及相遇持续时间均服从指数分布。因此，可根据历史信息，利用时间序列指数平滑预测方法估计节点间的相遇持续时间D，以及相遇间隔时间I，进而对节[56]点间的通信传输容量进行估计，如式(4.12)所示：CsrBDsr(4.12)其中Csr表示在源节点s与中继节点r之间的通信传输容量，B表示单位时间内发送的数据量，Dsr表示源节点s与中继节点r间的相遇持续时间。根据上文介绍的中继节点匹配算法，首先根据源节点s的邻居列表信息，匹配s出转发会话目标节点为dk的编码数据的中继节点入选节点，其入选节点集为Jd'，k并由集合内的节点负责转发会话目标节点为dk的编码数据。假定源节点s同一时lls刻最多与其中的一个入选节点rd(rddJ')进行通信，则在单位时间T内，源节kkkTCTsrlldk点s与入选节点rd平均相遇次数为，通信传输容量为，由此kDIllDIsrddkksrsrllsrddkk估算出源节点s与转发会话目标节点为dk的编码数据的所有入选节点间的通信传sJdk'CTlsrdk输容量总和最大为。l1DIllsrddkksr43 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制在中继节点的匹配过程中，不同会话目标节点所匹配的中继节点各不相同，在时间T内的通信传输容量总和存在差异，为了使得可能的最大通信传输容量得以充分利用，源节点s的编码速率Rencode需结合实际的组播传输容量做出相应的调整，具体如式(4.13)所示：sJdk'CTlsrdkmax{}l1DIsrllsr(4.13)Rddkk,k{1,2,...,}mencodeT考虑到对于部分的会话目标节点，通信传输容量总和较小，较大的编码速率易导致此类会话目标节点的编码数据在源节点的缓存中长时间滞留，占用较大的缓存空间，显然，编码速率不能设置太高。因此，本章将选择满足上述关系的最小编码速率，并且随着节点相遇持续时间以及相遇间隔时间的动态变化，编码速率Rencode也将随之进行调整。4.5数值分析本章采用机会网络仿真平台ONE对提出的组播路由机制性能进行验证，所采用的测试环境包括模拟器自带的基于地图的移动模型以及基于Infocom06实测数据的实测移动模型，仿真场景的参数设置如表4.1所示。所提出的对比组播路由机[30]制包括EBMR机制以及文献[52]所提出的TLMR机制。表4.1仿真参数设置参数数值仿真时间/h12仿真区域/m×m4500×3400节点运动模型基于地图模型/实测模型节点个数/个126/78节点通信方式蓝牙节点缓存大小/MB[5,100]传输范围/m10传输速度/kBps250TTL/min180时间窗口/s60衰减因子0.01数据大小/kB[200k,300k]44 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制EBMR机制是基于PRoPHET算法提出的一种组播路由机制，通过概率预测估算的方式选择与会话目标节点相遇概率更高的节点转发数据；TLMR机制结合了直接投递以及间接投递的方式转发数据，与前者不同在于运用了多跳转发，两种对比机制均采用单副本数据转发，即每个会话目标节点对应一个数据副本。本章以会话组大小以及节点移动速度为变量对三种组播路由机制进行了仿真，比较分析了三种组播路由机制在数据投递率、传输时延以及投递开销上的性能。4.5.1不同会话组大小下的网络性能会话组的大小代表着一个通信组中实际接收数据的会话目标节点数目的多少，有效的组播路由机制需保障不同会话组大小下的通信需求。本节仿真中的会话组大小被设定后，在整个通信过程中一个通信组中的会话目标节点以及数目将保持不变。不同会话组大小下的三种组播路由机制的网络性能如图4.2-4.4所示，下面将从数据投递率、传输时延以及投递开销三方面进行分析：图4.2中三种组播路由机制的数据投递率均呈现上升趋势，其原因在于会话目标节点数目的增多，携带数据的中继节点与会话目标节点相遇的可能增大，促进了数据投递。在基于地图模型下，本章提出的CCR-OMMR机制的数据投递率相比EBMR提高了16%，相比TLMR提高了11.1%；在实测模型下，CCR-OMMR机制的数据投递率相比EBMR和TLMR分别提高了36.5%，22.2%。本章提出的机制采用喷泉编码对原始数据进行编码，在传输过程中丢失的数据可通过冗余编码数据进行弥补，从而降低了数据丢失。此外，选择中继节点时考虑了节点的服务度，避免通过部分活跃度高但服务度低的节点转发数据，提高了数据成功投递率。而其他两种机制均采用单副本数据，对于缺少端到端反馈重传的机会网络，一旦数据副本丢失或者被转发到服务度低的节点，对应的会话目标节点将无法接收到该数据，数据投递率因此降低。由图4.3可知三种机制随着会话目标节点数目的增大，传输时延均有所增大。在基于地图模型下，本章提出的CCR-OMMR机制的传输时延相比其他两种机制较低，相比EBMR机制降低了13.2%，相比TLMR机制降低了5.6%；在实测模型下，提出机制的传输时延相比其他两种机制分别降低了13.9%，3.7%。其原因在于本章提出基于转发效用最优匹配的中继节点选择方法，同时指定多个中继节点并45 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制行传输编码数据到各个会话目标节点，提高了网络运行效率。而EBMR机制基于PRoPHET算法选择中继节点，为了选择较优的下一跳节点可能需要较长时间的等待，致使数据长时间滞留在中继节点缓存中。而TLMR机制通过估算多跳投递概率选择中继节点，数据可能经历较多次转发才能到达会话目标节点，这也会导致传输时延的增大。0.900.750.700.850.650.800.600.750.550.50数据投递率0.70数据投递率0.45EBMREBMR0.65TLMR0.40TLMRCCR-OMMRCCR-OMMR0.600.355101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图4.2不同会话组大小下的数据投递率2800270027002600260025002500/s2400/s240023002300传输时延传输时延220022002100EBMR2100EBMRTLMRTLMR2000CCR-OMMR2000CCR-OMMR5101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图4.3不同会话组大小下的传输时延图4.4描述了不同组播路由机制的投递开销情况，由于会话目标节点数目的增多，使得通信过程中较多组播路径得到共享，减少了数据转发。基于地图模型下和实测模型下，提出的CCR-OMMR机制相比TLMR机制投递开销较低，相比EBMR机制稍有增加。在仿真前期本章提出的CCR-OMMR机制投递开销较大，随后其下降趋势更为显著，原因在于本章引入了喷泉编码增加了部分冗余数据，46 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制使得网络中的数据转发量有所增大，但随着会话目标节点数目的增多，冗余数据提高了数据投递的可靠性，成功接收到数据的会话目标节点数目增多，其优势逐渐得到体现。此外，负载均衡的中继选择方式使得网络中较多的节点参与到数据的转发过程中，与会话目标节点直接相遇的机会增多，从而减少了不必要的中继转发，因此，投递开销呈现大幅度下降。4035EBMREBMRTLMRTLMR35CCR-OMMRCCR-OMMR30302525投递开销投递开销202015155101520253051015202530会话组大小/个会话组大小/个(a)基于地图模型(b)实测模型图4.4不同会话组大小下的投递开销4.5.2不同节点移动速度下的网络性能网络中节点移动速度的变化也是影响组播通信质量的一个重要因素。节点移动速度越快，整个网络拓扑的变化更加频繁，可靠的组播路由机制对于网络环境的变化须具有较强的适应性。本节中每个通信组中的会话目标节点数目为15，图4.5-4.7为三种组播路由机制在基于地图模型下数据投递率、传输时延以及投递开销上的性能。图4.5为三种组播路由机制的投递率受节点移动速度变化的影响情况。可见，随着节点移动速度的增大，成功投递的数据量呈现下降趋势。而本章提出的CCR-OMMR机制相比其他两种机制数据投递率较高，同时下降趋势相对平缓。节点移动加快，节点间连接持续的时间变短，使得数据转发的效率降低。本章提出的CCR-OMMR机制提出均衡节点转发负载，同时使较多有效的中继节点参与数据转发，而不是仅仅依靠部分转发效用较高的节点转发数据，这种转发模式很大47 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制程度上弥补了EBMR机制和TLMR机制在高移动速率环境下的不足。相比EBMR机制，本章提出的机制投递率提升了15.8%，相比TLMR机制提升了5.2%。图4.6直观地描绘了不同机制的传输时延随节点移动速度加快的变化情况，EBMR机制和TLMR机制的传输时延明显呈下降趋势，其原因在于节点移动速度加快，节点平均连接间隔时间减小，节点在中继节点处滞留的时间因此缩短，从而使得传输时延减小。而本章提出的机制随着节点移动速度的增大传输时延呈现缓慢上升趋势，主要原因在于节点移动速度增加，节点间连接持续时间变短，转发效用较高的节点的所能转发的数据量减少，更多的数据流经效用不是很高的节点转发，因而使得数据的传输时延稍有增大。综合来看，本章提出的机制传输时延相比其他两种机制分别降低了20.5%和1.9%。0.85EBMRTLMR0.80CCR-OMMR0.750.70数据投递率0.650.601234567节点移动速度/(m/s)图4.5不同节点移动速度下的数据投递率3000EBMR2800TLMRCCR-OMMR2600/s2400传输时延2200200018001234567节点移动速度/(m/s)图4.6不同节点移动速度下的传输时延48 重庆邮电大学硕士学位论文第4章编码速率受控的最优匹配组播路由机制图4.7为三种机制在不同节点移动速度下的数据投递开销，EBMR机制和TLMR机制的投递开销呈现上升的趋势，而本章的CCR-OMMR机制呈现略微下降，到后期甚至低于EBMR机制。EBMR机制和TLMR机制中选择将数据转发给与会话目标节点相遇概率较高的节点，节点移动的加快使得这类节点与会话目标节点有效连接时间变短，成功投递到会话目标节点的数据量减少，而网络中数据转发量并未减少，因而使得投递开销增大。本章提出的CCR-OMMR机制在估算节点转发效用时综合考虑到了节点中继服务的可靠性，避免选择与会话目标节点连接频繁但实际转发数据较少的节点作为中继节点，从而减少了不必要的数据扩散，数据转发开销因此得到控制。55504540投递开销35EBMR30TLMRCCR-OMMR251234567节点移动速度/(m/s)图4.7不同节点移动速度下的投递开销4.6本章小结为了提高组播通信的可靠性，同时均衡网络节点的数据转发负载，充分利用可能的相遇机会进行通信，本章提出了一种编码速率受控的最优匹配组播路由机制，通过估计节点到各个会话目标节点的转发效用，根据最优匹配算法为会话目标节点匹配中继节点，并由这些中继节点为其传输数据。同时，为了提高组播通信的可靠性，本章采用了喷泉编码并在估算组播通信容量的基础上对编码速率进行控制。本章提出的组播路由机制能够使得尽可能多的网络节点参与到组播通信过程中。仿真表明，该机制能够有效提高数据投递率，控制网络开销，同时在变化的网络环境中其性能也相对稳定。49 重庆邮电大学硕士学位论文第5章结束语第5章结束语5.1全文工作总结机会网络中通过“存储-携带-转发”的模式进行数据传输，因此，中继节点的选择直接影响着组播通信的效率。本文深入研究了机会网络中的组播路由机制，针对机会网络组播通信过程中所遇到的问题进行研究分析，并引入喷泉编码以提高组播通信的可靠性，同时综合考虑了社交网络中节点的社会属性以及节点的历史运行信息，最终提出了相关的解决方案。本文的主要研究进展如下：(1)现有的组播路由机制侧重于研究如何选择中继节点，较少考虑到数据传输的可靠性。针对这类问题，文中引入了喷泉编码对原始数据进行编码传输，各个会话目标节点接收到足够多的编码数据便可译码出原始数据。为了减少部分效用较低的编码数据的转发，结合喷泉编码的特性，本文在第三章提出了冗余数据检测算法对编码数据加以管理。同时在第四章提出根据组播通信容量动态调整编码速率，以达到控制网络负载的目的。(2)本文在第三章提出了一种带有社会关系感知的机会网络组播路由机制。在组播通信过程中，利用社交网络的特性对节点关系进行评估，结合节点的历史转发行为衡量节点直接或者间接转发数据的能力，最后针对不同类型的节点设计相应的标准以选择合适的中继节点转发数据。(3)网络中活跃度较高，转发能力较强的节点通常以较高的频率为其他节点转发数据，而较大的转发量将快速消耗此类节点的资源，进而影响网络的后续通信。本文在第四章提出了一种基于最优匹配算法选择中继节点的方法，通过衡量节点将编码数据转发到各个会话目标节点的转发效用，利用最优匹配算法为各个会话目标节点选择合适的中继节点，在发挥中继节点转发优势的同时使得尽可能多的节点参与到组播通信过程中，以优化网络运行效率。50 重庆邮电大学硕士学位论文第5章结束语5.2未来工作展望本文针对机会网络中的组播路由机制进行了深入研究，分析机会网络组播通信所面临的问题，结合机会网络的特性提出了相应的解决方案，并利用ONE仿真平台验证了机制的合理性及可行性。但是笔者认为本文的工作仍然存在不足之处：(1)文中涉及到对网络节点关系的感知，主要通过节点历史转发行为、历史相遇记录衡量节点之间的关系，但实际应用场景中，节点具有多种不同的社会属性，包括主观的和客观的，这些节点属性都将影响节点的数据转发行为，这是文中考虑不够全面的地方。因此，在未来的工作中，将通过多维社会属性评估节点的转发行为和转发能力，以提高中继节点选择的合理性。(2)其次，文中提出的基于相遇历史信息的评估方式要求节点存储大量的相遇信息，对于节点缓存资源受限的机会网络来讲，显然是一笔较大的资源开销。因此，为高效地利用节点缓存，有必要对缓存的数据加以管理。在未来的工作中，将对缓存的数据加以评估，尽可能存储效用较高的数据。(3)机会网络中的组播通信通常面临的问题是通信组成员的变化，即通信组中可能有新增加的或者从原通信组中离开的会话目标节点，而在本文研究中虽然提出了喷泉编码的方法保障各会话目标节点可靠接收数据，但相关研究还不够深入，在后续的工作中将加强这方面的研究。综上所述，本文当前对所得到的机制性能分析还不够全面，研究中仍有较多不足之处，对此将在以后的工作中做出改进。51 重庆邮电大学硕士学位论文参考文献参考文献[1]HindsA,NgulubeM,ZhuSY,etal.Areviewofroutingprotocolsformobilead-hocnetworks[J].InternationalJournalofInformationandEducationTechnology,2013,3(1):1-5.[2]ContiM,GiordanoS.Mobileadhocnetworking:milestones,challenges,andnewresearchdirections[J].IEEECommunicationsMagazine,2014,52(1):85-96.[3]MotaVFS,CunhaFD,MacedoDF,etal.Protocols,mobilitymodelsandtoolsinopportunisticnetworks:Asurvey[J].ComputerCommunications,2014,48(4):5-19.[4]HuangJH,AmjadS,MishraS.Asensorbasedtrackingsystemusingwitnesses[C]//Proceedingsofthe25thInternationalConferenceonDistributedComputingSystems.Columbus,USA:IEEEPress,2005:251-255.[5]HullB,BychkovskyV,ZhangYang,etal.CarTe1:Adistributedmobilesensorcomputingsystem[C]//Proceedingsofthe4thACMInternationalConferenceonEmbeddedNetworkedSensorSystems.Boulder,USA:ACMPress,2006:125-138.[6]JuangP,OkiH,WangYong,etal.Energy-efficientcomputingforwildlifetracking:Designtrade-offsandearlyexperienceswithZebraNet[J].2002,37(10):96-107.[7]HuiP,ChaintreauA,ScottJ,etal.Pocketswitchednetworksandhumanmobilityinconferenceenvironments[C]//ProceedingsoftheACMSIGCOMMWorkshoponDelay-TolerantNetworking.Philadelphia,USA:ACMPress,2005:244-251.[8]LindgrenA,PhanseKS.Evaluationofqueuingpoliciesandforwardingstrategiesforroutinginintermittentlyconnectednetworks[C]//FirstInternationalConferenceonCommunicationSystemSoftwareandMiddleware.NewDelhi,India:IEEEPress,2006:1-10.[9]叶辉,陈志刚,赵明.ON-CRP:机会网络缓存替换策略研究[J].通信学报,2010,31(5):98-107.[10]ChunPL,WingCL,ChingY.Threshold-basedopportunisticroutingprotocolinmulti-hopwirelessnetworks[C]//Proceedingsof19thAnnualWirelessandOpticalCommunicationsConference.Shanghai,China:IEEEPress,2010:1-6.52 重庆邮电大学硕士学位论文参考文献[11]NgN,ChangH,ZouZhongjian,etal.Anadaptivethresholdmethodtoaddressroutingissuesindelaytolerantnetworks[C]//GLOBECOMWorkshops.Huston,USA:IEEEPress,2011:1122-1126.[12]RashidS,HananA,AyubQ,etal.Dynamicpredictionbasedmultiqueue(DPMQ)droppolicyforprobabilisticroutingprotocolsofdelaytolerantnetwork[J].JournalofNetworkandComputerApplications,2013,36(5):1395-1402.[13]SymingtonS,FarrellS,WeissH,etal.Bundlesecurityprotocolspecification[C]//ProceedingsoftheWorkProgress.Washington,USA:IRTFPress,2011:1-60.[14]ManamVKC,MahendranV,MurthyCSR.PerformancemodelingofDTNroutingwithheterogeneousandselfishnodes[J].WirelessNetworks,2014,20(1):25-40.[15]LiYong,SuGuolong,WangZhaocheng.EvaluatingtheeffectsofnodecooperationonDTNrouting[J].AEU-InternationalJournalofElectronicsandCommunications,2012,66(1):62-67.[16]RestaG,SantiP.Aframeworkforroutingperformanceanalysisindelaytolerantnetworkswithapplicationtononcooperativenetworks[J].IEEETransactionsonParallelandDistributedSystems,2012,23(1):2-10.[17]ButtyanL,HubauxJP.Stimulatingcooperationinself-organizingmobileadhocnetworks[J].ACMMobileNetworksandApplications,2003,8(5):579-592.[18]FelegyhaziM,HubauxJP,ButtyanL.Nashequilibriaofpacketforwardingstrategiesinwirelessadhocnetworks[J].IEEETransactionsonMobileComputing,2006,5(5):463-476.[19]DiniG,LoDA.Towardsareputation-basedroutingprotocoltocontrastblackholesinadelaytolerantnetwork[J].AdHocNetworks,2012,10(7):1167-1178.[20]DjamaludinCI,FooE,CorkeP.EstablishinginitialtrustinautonomousdelaytolerantnetworkswithoutcentralisedPKI[J].Computers&Security,2013,39(4):299-314.[21]LeguayJ,FriedmanT,ConanV.DTNroutinginamobilitypatternspace[C]//ProceedingsoftheACMSIGCOMMWorkshoponDelay-TolerantNetworking.Philadelphia,USA:ACMPress,2005:276-283.[22]EshghiS,KhouzaniMHR,SarkarS,etal.Optimalenergy-awareepidemicroutingindtns[J].IEEETransactionsonAutomaticControl,2015,60(6):1554-1569.53 重庆邮电大学硕士学位论文参考文献[23]ZhaoWenrui,AmmarM,ZeguraE.Multicastingindelaytolerantnetworks:semanticmodelsandroutingalgorithms[C]//ProceedingsoftheACMSIGCOMMWorkshoponDelay-TolerantNetworking.Philadelphia,USA:ACMPress,2005:268-275.[24]JinZhigang,WangJia,ZhangSainan,etal.Epidemic-basedcontrolledfloodingandadaptivemulticastfordelaytolerantnetworks[C]//20107thInternationalConferenceonUbiquitousIntelligence&Computingand7thInternationalConferenceonAutonomic&TrustedComputing.Xi'an,China:IEEEPress,2010:191-194.[25]FengZhenxin,ChinKW.Ontheperformanceofepidemicbasedroutingprotocolsfordeliveringmulticastbundlesindelaytolerantnetworks[J].InternationalJournalofWirelessInformationNetworks,2014,21(2):133-153.[26]BhatiaR,LiLE.Characterizingachievablemulticastratesinmulti-hopwirelessnetworks[C]//Proceedingsofthe6thACMInternationalSymposiumonMobileAdHocNetworkingandComputing.Illinois,USA:ACMPress,2005:133-144.[27]YeQing,ChengLiang,ChuahMC,etal.OS-multicast:On-demandsituation-awaremulticastingindisruptiontolerantnetworks[C]//IEEE63rdVehicularTechnologyConference.Australia:IEEEPress,2006:96-100.[28]WangYunsheng,WuJie.Adynamicmulticasttreebasedroutingschemewithoutreplicationindelaytolerantnetworks[J].JournalofParallelandDistributedComputing,2012,72(3):424-436.[29]TripathiA.SpaceOptimizedMulticastinDelayTolerantNetworks[J].InternationalJournalofComputingandNetworkTechnology,2013,1(2):139-149.[30]XiYong,ChuahMC.Anencounter-basedmulticastschemefordisruptiontolerantnetworks[J].ComputerCommunications,2009,32(16):1742-1756.[31]WangYunsheng,LiXiaoguang,WuJie.Multicastingindelaytolerantnetworks:delegationforwarding[C]//2010IEEEGlobalTelecommunicationsConference.Florida,USA:IEEEPress,2010:1-5.[32]ErramilliV,CrovellaM,ChaintreauA,etal.Delegationforwarding[C]//Proceedingsofthe9thACMInternationalSymposiumonMobileAdHocNetworkingandComputing.HongKong,China:ACMPress,2008:251-260.[33]LoSC,LuoNW,GaoJS,etal.Quota-basedmulticastroutingindelay-tolerantnetworks[J].WirelessPersonalCommunications,2014,74(4):1329-1344.54 重庆邮电大学硕士学位论文参考文献[34]JiangGuoxing,ChenJun,ShenYanqing.Deliveryratio-andbufferedtime-constrained:multicastingfordelaytolerantnetworks[J].JournalofNetworkandComputerApplications,2014,44:92-105.[35]GaoWei,LiQinghua,ZhaoBo,etal.Social-awaremulticastindisruption-tolerantnetworks[J].IEEETransactionsonNetworking,2012,20(5):1553-1566.[36]DengXia,ChangLe.Amulticastroutingschemebasedonsocialdifferencesindelay-tolerantnetworks[C]//the4thInternationalConferenceonEmergingIntelligentDataandWebTechnologies.Xi'an,China:IEEEPress,2013:501-507.[37]DengXia,ChangLe.Atime-consideredmulticastroutingschemebasedonsocialdifferencesindelay-tolerantnetworks[J].InternationalJournalofEmbeddedSystems,2014,6(1):50-60.[38]WangWan,LiCao.ACore-basedCommunityDetectionAlgorithmforNetworks[C]//Proceedingsofthe4thIEEEinternationalConferenceonCASoN.SaoCarlos,Brazil:IEEEPress,2012:20-25.[39]WangYunsheng,WuJie,YangWS.Cloud-basedmulticastingwithfeedbackinmobilesocialnetworks[J].IEEETransactionsonWirelessCommunications,2013,12(12):6043-6053.[40]ChuahMC,YangPeng.Context-awaremulticastroutingschemefordisruptiontolerantnetworks[J].InternationalJournalofAdHocandUbiquitousComputing,2009,4(5):269-281.[41]SantiagoJ,CasacaA,PereiraPR.Multicastindelaytolerantnetworksusingprobabilitiesandmobilityinformation[J].AdHoc&SensorWirelessNetworks,2009,7(1-2):51-68.[42]LindgrenA,DoriaA,SchelenO.Probabilisticroutinginintermittentlyconnectednetworks[J].ACMSIGMOBILEMobileComputingandCommunicationsReview,2003,7(3):19-20.[43]MacKayDJC.Fountaincodes[J].IEEProceedings-Communications,2005,152(6):1062-1068.[44]LubyM.LTcodes[C]//Proceedingsofthe43rdAnnualSymposiumonFoundationsofComputerScience.Vancouver,Canada:IEEEPress,2002:271-280.[45]ZhuZhiliang,LiuSha,ZhangJiawei,etal.PerformanceanalysisofLTcodeswithdifferentdegreedistribution[C]//IEEE5thInternationalWorkshopon55 重庆邮电大学硕士学位论文参考文献Chaos-FractalsTheoriesandApplications.Dalian,China:IEEEPress,2012:142-146.[46]ChampelML,HugueninK,KermarrecAM,etal.LTnetworkcodes[C]//IEEE30thInternationalConferenceonDistributedComputingSystems.Genova,Italy:IEEE,2010:536-546.[47]吴大鹏,孔晓龙,张洪沛,等.社会属性感知的间断连接无线网络数据转发策略[J].通信学报,2015,36(1):38-47.[48]WuDapeng,ZhangPuning,WangRuyan.Residualresourcesawaredistributedadmissioncontrolmechanisminmobilemulti-hopnetwork[J].AnnalsofTelecommunicationsAnnalesdesTelecommunications,2013,68(9-10):553-568.[49]王朕,王新华,隋敬麒.机会网络模拟器ONE及其扩展研究[J].计算机应用研究,2012,29(1):272-277.[50]BuddeR,NowakS,KaysR.Reliablebroadcasttransmissioninvehicularnetworksbasedonfountaincodes[C]//IEEE73rdVehicularTechnologyConference.Budapest,Hungary:IEEEPress,2011:1-5.[51]GaoWei,LiQinghua,ZhaoBo,etal.Multicastingindelaytolerantnetworks:asocialnetworkperspective[C]//Proceedingsofthe10thACMInternationalSymposiumonMobileAdHocNetworkingandComputing.Louisiana,USA:ACMPress,2009:299-308.[52]LeT,KalantarianH,GerlaM.Atwo-levelmulticastroutingstrategyfordelaytolerantnetworks[C]//Proceedingsofthe14thAnnualMediterraneanAdHocNetworkingWorkshop.Algarve,Portugal:IEEEPress,2015:1-7.[53]WuDapeng,ZhangHongpei,WangHonggang,etal.Quality-of-protection-drivendataforwardingforintermittentlyconnectedwirelessnetworks[J].IEEEWirelessCommunications,2015,22(4):66-73.[54]ChakchoukN.ASurveyonOpportunisticRoutinginWirelessCommunicationNetworks[J].IEEECommunicationsSurveys&Tutorials,2015,17(4):2214-2241.[55]HanB,HuiP,KumarVSA,etal.Mobiledataoffloadingthroughopportunisticcommunicationsandsocialparticipation[J].IEEETransactionsonMobileComputing,2012,11(5):821-834.[56]吴大鹏,楼芃雯,刘乔寿,等.带有编码冗余控制的机会网络数据转发机制[J].通信学报,2015,36(3):1-12.56 重庆邮电大学硕士学位论文致谢致谢行笔至此，三年的研究生生涯即将落下帷幕。在这三年里，不论是研究学习还是为人处世，都让我受益颇多，而这些点点滴滴的收获都离不开曾经给予我无私帮助的人。在此毕业论文完成之际，我将由衷地向他们致以诚挚的感谢！首先感谢我的导师—杨静老师。三年来，杨老师严谨的科研作风、谦和的为人深深感染着我。从研究生学习生活的开始至今，杨老师一直悉心指导并鼓励着我，无论是学术研究还是工作生活，都尽其所能给予了我很多的关怀和帮助。同时也在困难之时开导鼓励我，正是她的支持，才让我勇敢地向前。很幸运也很感谢能成为她的学生。同时，我要感谢我的指导老师—吴大鹏老师。三年来，他的悉心指导和严格督促，让我成长了很多。作为我学术生涯的启蒙者，吴老师以他严谨的科研态度和刻苦的专研精神感染着我，并在硕士论文的选题、撰写和发表等各个阶段给了我很多的帮助和交流。在此诚挚地感谢吴老师的悉心指导。感谢王汝言老师、吉福生老师、刘乔寿老师、熊余老师、赵辉老师等，非常感谢你们在研究生期间给予我帮助；感谢实验室的王燕燕、张洪沛、周之楠等各位师姐师兄，感谢赵妍妍、闫俊杰、许稳、杨慧娉等同窗们，感谢缪懿、李无忧、汪雄、李兴等师弟师妹们，与你们结识是我莫大的荣幸，正是与你们无数次的交流才有了我在求学路上的不断进步；感谢我的舍友何芳、郭彦芳、郭慧兰，正是你们的陪伴，才让我的求学生涯不再枯燥。感谢大家，是你们给了我研究生生活有着如此美好精彩的回忆。感谢我的父母亲人，是你们一直以来的默默付出为我的学习生活提供了充足的保障，是你们一直以来的支持让我勇敢地面对一路的风雨坎坷，你们永远是我最坚强的后盾，感谢你们！我会尽我所能回报你们。最后，谨借此文向参与论文审阅的各位专家和老师们致以由衷的感谢，感谢您们的批评指导和提出的宝贵意见。57 重庆邮电大学硕士学位论文攻读硕士学位期间从事的科研工作及取得的成果攻读硕士学位期间从事的科研工作及取得的成果参与科研项目：[1]基于社会网络分析理论的机会网络服务发现策略研究(61001105)，国家自然科学基金(2013.09-2014.01)[2]社会化泛在无线网络节点关系感知与可信协同机理研究(61371097)，国家自然科学基金(2014.01-2016.03)发表及完成论文：[1]杨静,龚玲玲,杨正川,等.带有模糊控制的机会网络数据转发控制策略[J].系统工程与电子技术,2016,38(2):392-399.[2]甄岩,龚玲玲,杨静,等.带有社会关系感知的机会网络组播路由机制[J].华中科技大学学报.(已录用)[3]杨静,龚玲玲,张炎,等.编码速率受控的最优匹配组播路由机制[J].通信学报.(在审)58
