第三章第四章内容第章第四章内容.doc

第三章 一种基于AODV协议的改进算法 ３.１　AODV协议改进的必要性和可行性 3.1.1　AODV协议改进的必要性 AODV路由协议中基于路由发现和路由维护两个过程来建立网络中某两个节点之间的路径。整个路由发现又分为路由请求和路由相应阶段。对于路由请求阶段，洪泛消息形式广播RREQ报文目标节点；在路由响应阶段，目标节点优先选择最先到达的RREQ报文，进行发送RREP报文。这时，由于寻找路径时节点运动最为剧烈，发送消息时路由易断裂，这样会导致RREP报文的丢失。 在路由维护阶段，当断连节点广播RERR报文时，会将错误的数据报文丢弃并通知源节点重发请求报文，导致后续报文的延时；本地恢复时，为了消除新路径造成的回环，可能会造成下游节点发送的RRRP被丢弃，降低了路径恢复的几率。而且，尽管AODV具有路由维护机制，但由于节点是移动的，路由可能不会及时被修复或者修复失败，这样降低了网络控制信息的利用率，并且会导致路由时延的增加，由此影响网络的性能。 所以经典的AODV协议虽然在控制信息以及带宽利用上做了很多优化，但是当面临节点移动情况混乱或其他不可控的拓扑时，基于洪泛的路由发现和维护过程便会可能造成网络拥塞，影响网络的数据流通效率甚至暂时性的瘫痪。 3.1.1　AODV协议改进的可行性 考虑到AODV协议机制中先天不足的部分，本文将结合机会网络(opportunistic networks，OppNets)的“携带—存储—转发”机制思想，对经典AODV做出一些改进设计，使得其在工作的时候避免网络拥塞，并提高包裹交付几率。 现有的AODV协议工作的基本原理是节点首先通过路由发现和路由维护找到目的路由，然后将路由信息存入路由表，然后进行数据包的传送。这个过程中，路由层和传输层是相对独立工作的，也就是说，路由层协议的任务是随时发现有效的路由并且建立路由表，传输层的任务是在需要发送数据包信息的时候查询路由层建立的路由表并且将信息交付出去。这样的分工方式奠定了通信系统整体高效运作的基础，但是同时当面临“特殊情况”时，比如拓扑高度不稳定造成的路由表失效率的迅猛上升、路由层请求和维护信息的大量泛洪，这会使得路由层工作量的超负荷，同时传输层无法得到有效的路由信息也会使数据的传输造成明显的延迟。 这意味着在Ad Hoc这样节点动态移动的特殊的网络中，如果路由层执行传统的AODV协议，这样的情况是必然发生的。一旦路由层崩溃，传输层的工作也会受到严重影响。所以，这种层之间分工的模式在某些极端的情况反而变得低效。 与AODV协议先找到路由在传输数据的机制相对立，机会网络(opportunistic networks，OppNets)的“携带—存储—转发”机制是在节点仅在找到下一跳时便将数据包裹同时发送出去，考量符合下一跳节点的方式一般是依照拓扑信息中节点的运动规律，得出最有可能连通到目的节点的中继节点。这样跨层执行的优势就是增加了包裹成功交付的概率，但是需要执行较复杂的计算以及需要较多的存储空间，对设备的要求较高。 机会网络往往是在军方设备中实现的，而在目前在民用领域中，适合推广Ad Hoc网络的设备一般是手机、平板电脑等“轻设备”，这些设备的共同的特点是数据处理能力有限、电池电量有限。所以这就限制的复杂的机会网算法的应用，针对“轻设备”，是否可以设计一种计算简单同时符合机会网络思想的“轻算法”呢？ 本文提出了一种结合了机会网络“携带—存储—转发”思想的应用于传统AODV协议中的改进算法，即“载体选举算法”，载体选举算法是基于每一个节点都参与到工作之中的视角中来描述的。该算法直观上是针对一条未发送的信息（其目的节点在失去联系的情况），源节点能够将信息发送到尽可能处于最广范围的互联节点中去。因为本设计所考虑的节点处于非快速的移动情况，这样即将进入互连范围的运动节点就有更高的可能性接收到完整的信息，通过对节点的运动状态以及间歇性连通特性的研究，对合格有效的节点进行筛选会大大降低开销提高效率。在此需要强调的是，载体选举算法并不是覆盖了传统AODV中的路由发现和维护机制，而是当原机制失效时，一种补救的机制。该算法并不是对AODV的否定，而是一种补充。 ３.2　载体选举算法（Candidate Carrier Algorithm）算法设计 在Ad Hoc网络中，有三类重点研究对象，即源节点、中继节点和目的节点。在“载体选举算法”中针对该三类节点同样需要制定不同的策略，对于目的节点来说只需要比对请求信息中的目的节点是否是自身即可，对于源节点和中继节点而言，则需要执行一些特别的步骤： 3.2.1　针对源节点 当节点S无法找到去往D的路径时，或者已经建立的路径丢失，它会缓存一个用于D节点的信息m并且请求其所有的临近节点列表中的临近节点。通过两跳邻节点信息，节点S选出一