《时机网络中的缓存路由算法（精品）.docx》由会员分享，可在线阅读，更多相关《时机网络中的缓存路由算法（精品）.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、时机网络中的缓存路由算法摘要：时机网络是一种通过节点移动建立通信链路的无线自组织网络，一般通过消息复制的路由策略传递信息。但该方式将导致链路中存在大量消息副本，对节点缓存构成宏大压力，造成网络拥塞。针对该情况，结合Prophet算法，充分考虑节点缓存对链路状态及传输概率的影响，设计限制消息最大副本数量与及时删除节点缓存中不必要数据包的缓存管理机制，同时在Prophet算法中考虑了缓存比因素。仿真结果表明，该算法能够有效提高消息投递率，降低网络消耗。关键词：时机网络；Prophet算法；缓存区管理；拥塞控制怎样在不需要提早建立端到端链路的情况下，利用设备的移动性快速构成自组织网络，到达在网络中进
2、行消息传递的目的，是目前无线自组织网络研究中的热门。在紧急情况下，经常会碰到原有链路被毁坏，需要通过现有设备建立一条新链路的情况，怎样在该情况下进行有效的数据传输是目前需要解决的一个难题。为此，研究人员结合MANETMobileandAdHocNetwork与DTN1Delay-tolerantNetwork的特点，提出时机网路OpportunisticNetwork的概念2。时机网络是一种不需要源节点与目的节点之间存在一条完好链路，而是通过节点移动经过中构成的相遇时机建立通信的自组织网络。时机网络相对于传统网络表现出更好的适应性，愈加符合自组织网络的要求，因而近年来引起国内外研究者的广泛关注
3、，并开展了大量应用研究，如在灾难发生的紧急状况下构建自组织网络3，以及可用于观察海洋生物种群4与监察自然环境下放牧系统5的移动自组织网络等。由于时机网络是以“存储携带转发的路由机制形式开展工作的，在该形式下要求网络提供节点的可靠性保证，节点在未选取好下一跳转发节点时，中间节点不能丢弃数据6-7。当网络中的大量数据需要被传输时，节点的缓存利用率较高，易造成网络拥塞，影响数据正常传输。因而，在时机网络中，拥塞控制是保证网络稳定性与可靠性的关键因素。时机网络中针对拥塞控制情况有下面两种解决方法：限制消息副本数量，避免生成不必要的数据包。消息在链路中一般采用消息复制方式传输给下一跳节点，对于未对消息副
4、本进行合理控制的路由算法而言，在消息传输经过中，网络中会存在大量消息副本，因此极大地影响了网络性能7。针对该问题，文献8、9提出限制消息副本数量的路由机制，以减少因生成大量不必要数据包对网络造成的压力；及时删除不必要的数据包。当网络中的数据包已传输成功或不需要传输时，数据包若还滞留在节点缓存中，易造成节点缓存溢出，不仅导致数据无法得到及时传输，更极大地浪费了网络资源。因而，针对不必要的数据包，能够使用DLR、DL、DOA、DY等删包方式进行处理9-10。为避免网络出现拥塞状况，保证网络即便在高吞吐量的环境中也能正常传输数据是本文的研究重点。ProphetProbabilisticRouting
5、ProtocolUsingHistoryofEncountersandTransitivity算法通过比拟节点之间的相遇概率，选择能否将消息转发给中间节点。该工作机制可大幅减少网络中的副本数量，但还没有完全考虑到消息副本数量对节点缓存的影响。本文结合Prophet算法特点，提出控制消息副本数量以及考虑节点剩余缓存以避免拥塞的机制，进而有效提高消息投递率。1相关工作时机网络中的节点是具有移动性，且不稳定的，源节点与目的节点之间不存在一条已连接好的端到端的途径，即便在链路断开的情况下，可以以实现消息的逐跳转发，并成功传输消息。因而，其能够看成是具有一般DTN网络特征的无线自组织网络，愈加符合自组织
6、网络的需求11-12。目前，基本的时机路由算法能够分为两大类13：基于复制的路由算法与基于效用的路由算法。基于复制的路由算法是通过复制消息副本传输数据，在网络中构成多消息存储的路由策略，典型路由算法有Epidemic算法等9；基于效用的路由算法是以一个效用值为衡量标准，为中间转发节点的选取提供参考因素。本文讨论的Prophet算法即是根据节点之间的转发概率挑选节点，进行数据转发10。在基于复制与基于效用的经典算法中，未考虑到消息副本数量太多对节点缓存的影响，导致网路性能下降，因而具有一定局限性11-12。Prophet是一种基于概率转发的路由算法，节点在选择下一跳节点时会根据相遇概率传输消息，
7、节点之间的概率在相遇时升高，分开时则随着时间延长而降低。Prophet算法的工作机制是只要碰到比本人传输概率大的节点则会复制一个消息副本给对方。基于效用的转发方式固然在一定程度上控制了消息的转发副本数，但还没有减少不必要消息对节点缓存的影响。当节点接收新消息时，会判定本人能否有足够的缓存区，假如缓存区不够，则根据消息在缓存区的时间长短删除数据包，在缓存区中时间越长的数据包越容易被删除。因而，需要设置一个消息的生存期时间以控制消息生命长短，以便于删除不必要的数据包。传统Prophet算法是通过比拟相遇节点与目的节点的概率值决定能否将消息传输给相遇节点，假设a、b两点相遇，a、b两节点的概率值通过
8、式1进行更新。式中，Pinit是预先设置的两节点之间的初始概率，是老化因子，0，1，k表示距离上一次更新的时间长度。Prophet算法的概率还具有传递性，即a节点与b节点经常接触，b节点与c节点也经常接触，则节点b可作为节点a和节点c消息转发的中间节点，节点a、b、c的传递概率可根据公式3进行更新。3式中，是一个常数，0，1，其决定了消息经过中间节点传递后对整体数据传输成功概率的影响。固然Prophet算法中概率的传递性能够有效减少数据广播引起的拥塞现象，但一旦拥塞现象发生，会极大地影响算法性能。如图1所示，若节点a、b与节点b、c都能够经常保持连接，根据Prophet算法的传递性，b节点即可
9、作为a、c节点传输链路上的中间节点，并保持较高的投递率，但若b节点的缓存此时正处于拥塞状态，a、c节点链路上的数据包则无法正常转发。所以即便Prophet算法根据概率值的传递性选取了最好的中间转发节点，但若未考虑到中间节点的缓存情况，则无法合理地发挥该算法优点。假如此时a节点将消息转发给b节点，该消息则会溢出，否则a节点只能将消息保存在本地中，等待下一个适宜节点进行转发。2Prophet算法改良固然Prophet算法根据概率效用值选择转发节点的工作机制已在一定程度上减轻了网络中的拥塞情况，但仍未考虑节点缓存对算法性能的影响。时机网络是一个以“存储携带转发形式工作的自组织网络，一个节点假如处于链
10、路中的关键位置，则其需要转发的消息越多，而消息数量及大小与该节点缓存情况密切相关。假如节点缓存情况能够得到有效管理，则会提高消息传输的成功率。在网络中，消息数量及大小都是随机的，但节点缓存却是固定的，只要对节点缓存情况进行有效控制，才能保证后续消息得到正常转发11。2.1节点缓存比本文不仅针对节点缓存提出了有效的管理机制，还添加了缓存比效用因素，即算法在基于相遇概率选择转发节点基础上，同时考虑了节点缓存情况，选择转发成功率较高与缓存压力较小的节点作为转发节点。该方法能愈加有效地避免拥塞现象产生，增加数据包投递率。节点缓存比定义如下：式中，mi表示消息数量，Si表示消息大小，Btotal表示节点
11、缓存大小。2.2节点缓存管理机制本文提出的控制节点缓存数据包数量的管理机制主要包括下面两方面：1限制消息在传输经过中的最大副本数。由于Prophet算法在传输消息时是通过复制消息副本的方式工作的，没有限制消息的最大副本数，当消息在网络中传递且数量足够多时，能够揣测该消息已成功传输，此时再复制该消息副本无疑将给网络带来更大压力。因而，为每一个消息设置最大副本数量，当到达该上限时则停止复制消息，能够减少网络冗余。2及时删除已传输成功的消息。已传输成功的数据包在网络中是无用的，并且会极大地占用缓存。其不一定是长期滞留在缓存中的老数据包，可以能是新包传输成功，但未被及时删除。及时删除已传输成功的数据包
12、能够有效改善缓存情况，减少资源浪费。3路由算法设计本文提出的改良Prophet算法的核心思想在于控制节点缓存区，包括限制消息最大副本数目与及时删除网络中不必要的数据包。针对以上两点操作能够有效降低缓存区压力，保证节点不会因缓存区溢出导致消息无法正常传输。在此基础之上，Prophet算法在选择转发节点时进一步考虑了缓存比因素，其改良算法步骤如下：1a、b节点通过移动进入相互通信范围，建立连接。2两节点交换相互在本地保存的与链路中其它节点的传递概率。3根据式2计算节点a、b的传递概率，并考虑此时节点b缓存比Rb的情况。4节点a中有传输到目的节点s的消息，但该消息并不存在于节点b中，此时比拟Pa，s
13、与Pb，s*Rb大小，若Pa，sPb，s*Rb，则讲明b节点传输成功率更高，选择复制该消息副本给节点b，反之则不复制。4实验仿真与性能分析4.1实验仿真设置本文使用仿真工具ONE12OpportunisticNetworkEnvironmentSimulator对改良算法进行实验分析及性能比拟，验证本文提出的改良算法能否能够有效改善网络性能、解决拥塞情况。本文模拟了一些经典场景下节点移动的消息传递情况，如学校、社区及工作区，这些场景的节点移动范围都存在一定规律性，但节点移动速度和方向是随机的。采用移动模型模拟这些移动场景，实验参数如表1所示。在上述场景下，本文分别对原Prophet算法、改良后
14、的Prophet算法和Epidemic算法从网络性能的3个方面进行比拟，分别是传输成功率、网络开销和传输延迟，比拟在节点数量逐步增加时网络性能的差异。4.2仿真结果与分析本文对原Prophet算法、改良后的Prophet算法和Epidemic算法在不同节点数量时表现出的网络性能进行测试，仿真结果如图2-图4所示。在图2中，随着节点数量的增加，由于原Prophet算法和Epidemic是通过复制消息的方式在网络中传输的，节点数量较多会增加节点之间的接触概率，导致消息副本在网络中的数量不断增加。当缓存溢出时，消息则无法得到正常传输。改良后的Prophet算法考虑到了缓存情况，假设节点缓存已经溢出，
15、则该节点不会被选为下一跳节点，而是寻找其它合适的节点进行传递，使消息能够正常传输。在图3中，随着节点数量的增加，改良后的Prophet算法由于对缓存进行了管理，避免了消息在转发时选择缓存使用率高的节点，进而降低了算法开销，所以其网络开销一直保持在一个较低水平。但其它两个算法都是基于消息复制的路由算法，随着网络中消息副本的数量不断增加，并且没有解决节点缓存问题，因而易造成网络拥塞，增加网络开销。在图4中，改良Prophet算法在传输时间上多于其它两种算法，主要由于改良Prophet算法控制了网络中的消息副本数量，进而减少了与目的节点的相遇时机，在一定程度上也增加了消息传输到目的节点的时间，所以传输经过中比其它两个在网络中消息副本较多的算法花费时间更多。还有一个原因是在没有找到适宜的转发节点时，节点会将消息保存在本地，直到碰到适宜的下一跳节点才开场传输，进而导致传输延迟。本文分析了时机网络中存在的消息冗余情况，提出了设置消息最大副本数量与及时删除不必要数据包的节点缓存管理机制，并在Prophet算法基础上考虑了缓存比因素，设计了一个考虑节点缓存的改良Prophet算法。仿真结果表明，在一样条件下，改良算法相比于原Prophet算法及Epidemic算法，具有更高的消息投递率，能够有效防止网络拥塞情况发生，提高网络吞吐量。