一种改进的PROPHET路由算法

1、一种改进的 PROPHET路由算法摘要：在机会网络这种特殊的网络环境中，传统的路 由算法消耗资源太多，不适宜用于这种网络。本文对设计模 式为“存储一携带一转发”的Epidemic Routing算法和基于概率估计思想的 PROPHET算法进行了分析，针对这两种算 法的不足，利用节点接触频率和接收信号强度指示值RSSI(Received Signal Strength Indication ),并加入一种消息到达 通告机制，该机制用以抑制已达消息副本的扩散，提生了一 种改进的PROTHET算法。该算法不需额外设备支持，不依 赖于既存的网络拓扑结构。仿真结果表明，改进的 PROTHT 算法明显减小

2、了网络通信量，从而降低了节点能耗，改善了 网络状况。关键词：机会网络；RSSI; PROPHET ; Epidemic中图分类号：TP393.04文献标识码：A文章编号： 1007-9599 (2011) 03-0000-03One Improved PROPHET Routing AlgorithmYang Lei(College of Computer Science,Sichuan University,Chengdu610065,China)Abstract:Opportunity to network in this particular network environment, t

3、he traditional routing algorithm too muchconsumption of resources,not suitable for such networks.This design pattern is "storage-carry-forward, "the epidemic routing algorithms and ideas based on probability estimates PROPHET algorithm analysis,for lack of the two algorithms, using the nod

4、e access frequency and received signal strength indication RSSI (Received Signal Strength Indication),and add a message arrival notification mechanism,which copies the message to suppress the proliferation of already proposed an improved PROTHET algorithm.No additional equipment to support the algor

5、ithm does not depend on the existing network topology.Simulation results show that the improved PROTHT algorithm significantly reduced the network traffic,thereby reducing the node energy consumption,improve the network condition.Keywords:Opportunity to network;RSSI;PROPHET;Epidemic机会型网络是当前无线网络领域最新的

6、研究热点之一， 机会型网络涵盖了很多类型的网络，包括野生动物跟踪网络 1、传感器网络2、手持设备交换网3、运输网络4等。 文献5给由了机会型网络的一个描述性定义：机会型网络是一种特殊的移动自组网络，其中的移动节点通讯距离有限， 而在整个部署区域中节点是稀疏分布的(在局部可以是密集 的)，网络中由于节点运动而经常发生网络断连。机会型网络是移动自组网的一个重要演化。在机会型网 络中，通过节点的移动、相遇和转发来实现在不连通的网络 环境的通信，传统的移动自组网路由算法不能在这种网络环 境下有效地运作。提高数据到达率、尽可能减小数据传输的 延迟、减少数据传输过程中总的资源消耗、尽量减少网络对 基础设施

7、的依赖等是机会型网络路由算法的重要研究内容。目前，研究者已经提由了一些适用于机会型网络的路由 算法，如感染路由(Epidemic Routing ) 6、CAR(Context-Aware Routing ) 7、PROPHET8、PREP(PRioritized EPidemic ) 9等，这些适用于机会型网络的路 由算法通常被称为机会网络路由算法。Epidemic路由算法和PROPHET路由算法是其中的两种经典算法。本文借鉴PROPHET路由算法的优点，结合节点接触频 率，接触历史和接收信号强度指示值信息，提生了一种改进 的 PROPHET 路由算法：PROPHET-RT。一、Epidem

8、ic路由算法和 PROPHET路由算法简介Epidemic路由算法是最早应用于机会型网络的一个路由算法。该算法的主要设计思想是“存储一携带一转发”，消息的转发采用洪泛机制，在网络资源充裕的情况下，路由 扩散可能是最优解决方案，因为消息可以在最小延迟内到达 目标节点。然而，在机会型网络中，节点处理能力、节点能 量、节点缓存大小、网络带宽等资源往往都是有限的，无法满足Epidemic路由算法对资源的消耗。PROPHET路由算法是 Epidemic路由算法的一个改进算 法，是一种概率估计路由，中间节点根据传输成功率决定是 否转发数据，实现有选择地转发数据包。但是 PROPHET算 法没有考虑节点之间

9、的连接强度，只要节点进入另一个节点 的通信范围就等同看待，这显然不太合理。并且算法没有解 决已达消息继续在网络中扩散的缺点。二、PROPHET-RT路由算法RSSI ( Received Signal Strength Indication ),被普遍应用 于无线传感器网络中的定位技术，但极少用于路由算法设 计。RSSI是节点间互相通信时所接收到对方的信号强度大 小，利用RSSI建立机会概率值，一定程度上体现了节点问 连接的质量，同时又不需要大量的交互报文，对节点处理能 力有限的机会型网络来说是非常有利的。RSSI大小很大程度上可以指示两个节点转发数据成功率的大小，可以利用RSSI的这个特性来

10、设计路由算法。首先介绍一下RSSI值与节点间距离d的关系。(1)其中，n为信号强度常量d为发送者与接收者之间的距 离A为距离为一米时接收到的信号强度通过实验，A值的最佳范围为45-49, n值最佳范围为3.25-4.5,(一)传输概率的计算方法在PROPHET-RT算法中，每个节点 A维护1张其到每 个已知目的节点 B的传输概率表TP_Table。该表中记录着该 节点到其他节点传输概率值 PA (B) 6 0, 1,用来表示数 据包从该节点到B节点成功传输的概率。1 .节点A和网络中奥一已知目的节点B接触后，根据本节点接收的节点B到节点A的RSSI值、接触时间和接触频 率更新节点A到节点B的的

11、传输概率，如(2)式所示。(2)其中，PA (B)是原始的两节点间的传输概率；RSSI为信号强度值，该值一般为负；为常数，根据节点能接收到的RSSI而定，1为两节点在以往接触历史中总的接触 持续时间；C表示在接触历史中总的接触次数；反映了两节点每次接触的平均持续时间，表示了节点平均接触持续单位时间数；(大于1的整数)为持续时间对概率的影响因子；T为单位时间常量，根据实际网络情况设定。每个节点 到其他节点的机会概率初始值均为0,当节点A和其他节点相遇则更新机会概率值；RSSI值和 越大，则传输概率增加的越快。公式(2)改进了文献8中提由的计算方法，引入了节 点间接收信号的强度指示值RSSI和接触

12、时间。PA (B)的计算既考虑了节点接触的频率又考虑了节点间接触时接收到的信号强度指示值和接触时间（2） 果两节点长时间未接触，两者之间成功传递数据包 的可能性将变小。本文在此种情况下沿用文献8中提由的方 法计算传输概率，如式（3）所示。（3）其中t为自上次两节点接触后到现在的时间；U为单位时间常量；r60, 1为消解指数，用来表示老化时间对传输 概率的影响程度。3.PROPHET-RT的传输概率具有传递性。 如果节点A经 常与节点C接触，节点C又经常与节点D相遇，那么A极 可能通过节点C成功地将数据包转发给 D ,则A到D的预 测传输概率较大。当节点 A与节点C接触后，节点A根据 收到的节点

13、C的传输概率更新其到 D的传输概率，这种情况 沿用文献8中提由的计算方法，如（4）式所示。（4）其中，bS 0, 1为缩放常数，反映传输概率的传递性所 能影响的范围。（二）消息到达通告机制在PROPHET-RT路由算法中，加入数据包到达通告机制 来解决已达消息副本的继续扩散。为了标识已经到达的数 据，每个节点内设置一个 arriveAim容器，该容器记录已经 达到目的节点的数据分组 ID号，当数据到达目的节点时，目标节点将该数据分组的ID号写入自己的arriveAim。两个节点相遇后，先根据对方的arriveAim中的值置换由已经到达目的节点的数据分组，两个节点交换数据之前先删除已经 到达目标

14、的数据分组，从而有效防止已经到达目标的数据包 在网络中继续存在并扩散。（三）数据包转发机制下面以节点a和节点b接触时的处理过程为例说明整个 网络的数据包转发策略。1 .a和b接收到对方的 arriveAim 后，根据这个arriveAim 中的值置换由已经到达目的节点的数据分组，然后删除缓存 中的这些数据包；2 .a和b交换彼此的数据包摘要向量SV（summary vector）和根据历史接触记录维护的传输概率表TP_Table;3 .a收至U TP_Table-b,与自己的进行比对，根据式（2）和式（3）更新Pa （b）;如果TP_Table-b中存在较大的传输 概率Pb （X）, X=c,

15、 d，则表示b经常与网络中莫些节点（c, d）接触，a会据此根据传输概率传递性按式（4）更 新其到（c, d）的传输概率。类似的 b也根据收到的 TP_Table-a更新自己的传输概率表；4 .a更新完TP_Table-a之后，节点a对比SV-a和收到的SV-b,由此判断哪些数据包是 b没有的，然后根据这些数据 包的目的地址，逐个将其在TP_Table-a中的传输概率与TP_Table-b中的值进行比较，满足 TP_Table-a小于 TP_Table-b的消息逐条发送给 b节点，b收到数据包后，更 新SV-b,并以相同方式选择数据包发送给a, a节点收到之后更新SV-a。三、模拟实验和结果分

16、析为了评估PROPHET-RT路由算法的可用性和有效性，我们对PROPHET路由算法和PROPHET-RT路由算法进行了实 验仿真。算法的性能主要从数据包交付率、端到端延迟、平 均端到端跳数、节点平均使用的缓存大小进行评估。（一）实验设置1 .仿真场景设置。场景设置为800mx 800m的矩形范围， 分别选取30-100个节点在场景内随机产生目标位置进行移 动，运动速度在0-20m/s之间随机选择，节点通信半径为50m o 系统运行过程中产生 2000个数据包，每个数据包生成的时 间间隔为1s,数据包的源和目标由系统随机选择，数据包全 部生成后系统继续运行 2000s以实现数据包的转发。2 .

17、参数设置。这种网络在实际应用中，节点的缓存空间 是相当有限的，所以这里限制缓存空间最多容纳100个数据分组。数据包最大转发跳数限制为10跳，消解指数r设置为0.98,缩放常数b设置为0.25.（二）实验结果分析在缓存空间有限的情况下，由图1（ a）可知PROPHET-RT较PROPHET算法和Epidemic算法时延稍微要长， 但是相差 不多。由图1 (b), PROPHET-RT的数据包交付率是三者当 中最高的。由图1 (c), PROPHET-RT算法在资源消耗上较 Epidemic算法和PROPHET算法都有了明显的减少，消耗的 内存空间要小得多。由图1 (d), RSS-PROPHET

18、算法明显减小了数据包交付过程中转发的次数，可以有效减少带宽、 能源等的资源消耗。四、结束语本文针对机会型网络提由一种改进的概率估计机会网 络路由算法PROPHET-RT,将节点接触频率和接收信号强度 指示值RSSI以及节点间接触时间引入算法，有效利用了节 点间的接触频率和连接质量来设计数据包的转发策略。此 外，为了抑制已达消息及其副本在网络中继续扩散，算法引 入消息到达通告机制，减少了节点的资源消耗和网络的负 担。本文给由了传输概率的计算方法和数据包的转发策略， 实验结果表明，该算法较Epidemic和PROPHET减少了数据 包转发的次数，明显减小了设备缓存空间的消耗，在资源有 限的条件下，

19、极大地提高了数据包交付率。参考文献：1Juang P,et al.Energy-efficient Computing for WildlifeTracking:Design Trade-Offs and Early Experiences withZebraNetJ.ACM SIGPLAN Notices,2002,37:96-1072Wang Y , Wu H.Delay.Fault-Tolerant Mobile Sensor Network ( DFT2MSN ) :A New Paradigm for Pervasive Information GatheringJ.IEEE Tra

20、nsactions on Mobile Computing,2007,6,9:1021-10343Jing S,James S,et al.Haggle:Seamless Networking for Mobile ApplicationsC.Proceedings of the Ninth International Conference on Ubiquitous Computing ( UbiComp 2007) .Innsbruck,Austria,20074John B,Brian G,David J.et al.MaxProp:routing for vehicle-based disrupt