无线自组织网络AODV协议的仿真

无线自组织网络AODV协议的仿真 【实验目的】 在NS-2仿真AODV协议，并在trace文件中了解AODV协议的原理。【实验原理】1、AODV简介AODV是由Nokia研究中心的CharlesE.Perkins和加利福尼亚大学SantaBarbara的ElizabethM.Belding-Roryer以及Cincinnati大学SamirR.Das等共同开发，已经被IETFMANET工作组于2003年7月正式公布为自组网路由协议的RFc标准。AODV实质上就是DSR和DSDV的综合，它借用了DSR中路由发现和路由维护的基础程序，及DSDV的逐跳(Hop-by-Hop)路由、目的节点序列号和路由维护阶段的周期更新机制，以DSDV为基础，结合DSR中的按需路由思想并加以改进。AODV在每个中间节点隐式保存了路由请求和应答的结果，并利用扩展环搜索的办法来限制搜索发现过的目的节点的范围。AODV支持组播功能，支持QoS，而且AODV中可以使用IP地址，实现同Internet连接，但是不支持单向信道。和DSDV保存完整的路由表不同的是，AODV通过建立基于按需路由来减少路由广播的次数，这是AODV对DSDV的重要改进。和DSR相比，AODV的好处在于源路由并不需要包括在每一个数据分组中，这样会使路由协议的开销有所降低。AODV是一个纯粹的按需路由系统，那些不在路径内的节点不保存路由信息，也不参与路由表的交换。AODV协议可以实现在移动终端间动态的、自发的路由，使移动终端很快获得通向所需目的的路由，同时又不用维护当前没有使用的路由信息，并且还能很快对断链的拓扑变化做出反应。AODV的操作是无环路的，在避免了通常Bellman-ford算法的无穷计数问题的同时，还提供了很快的收敛速度。AODV的路由表中每个项都使用了目的序列号(DestinationSequenceNumber)。目的序列号是目的节点创建，并在发给发起节点的路由信息中使用的。使用目的序列号可以避免环路的发生。AODV使用3种消息作为控制信息:RouteRequest(RREQ)，RouteReply(RREP)和RouteError(RERR)。这些消息都在UDP上使用654端口号。当源节点需要和目的节点通信时，如果在路由表中已经存在了对应的路由时，AODV不会进行任何操作。当源节点需要和新的目的通信时，它就会发起路由发现过程，通过广播RREQ信息来查找相应路由。当这个RREQ到达目的节点本身，或者是一个拥有足够新的到目的节点路由的中间节点时，路由就可以确定了。所谓“足够新”就是通过目的序列号来判断的。目的节点或中间节点通过原路返回一个RREP信息来向源节点确定路由的可用性。在维护路由表的过程中，当路由不再被使用时，节点就会从路由表中删除相应的项。同时，节点会监视一个活动路由(activeroute，有限跳的，可用于数据转发的路由表)中，下一跳节点的状况。当发现有链路断开的情况时，节点就会使用RERR通知上游的节点，而上游的节点就会使用该RERR分组拷贝通知更上游的节点。在RERR消息中，指明了由于断链而导致无法达到目的节点。每个节点都保留了一个“前驱列表”(precursorlist)来帮助完成错误报告的功能，这个列表中保存了把自己作为到当前不可达节点的下一跳的相邻节点(可以通过记录RERR很容易地获得)。在路由表中，针对每一个表项，需要记录相应的的特征内容。其中，序列号是防止路由环路的关键所在。当发生断链时，通过增加序列号和度量值(跳数)来使路由表项无效。2、AODV路由协议的运行方式(a)AODV路由发现AODV路由协议是一种典型的按需驱动路由协议，该算法可被称为纯粹的需求路由获取系统，那些不在活跃路径上的节点不会维持任何相关路由信息，也不会参与任何周期路由表的交换。此外，节点没有必要去发现和维持到另一节点的路由，除非这两个节点需要进行通信。移动节点间的局部连接性可以通过几种方法得到，其中包括使用局部广播Hello消息。这种算法的主要目的是:在需要时广播路由发现分组一般的拓扑维护;区别局部连接管理(邻居检测)和一般的拓扑维护;向需要连接信息的邻居移动节点散播拓扑变化信息。AODV使用广播路由发现机制，它依赖中间节点动态建立路由表来进行分组的传送。为了维持节点间的最新路由信息，AODV借鉴了DSDV中的序列号的思想，利用这种机制就能有效地防止路由环的形成。当源节点想与另外一个节点通信，而它的路由表中又没有相应的路由信息时，它就会发起路由发现过程。每一个节点维持两个独立的计数器:节点序列号计数器和广播标识。源节点通过向自己的邻居广播RREQ(RouteRequests)分组来发起一次路由发现过程。(b)反向路由的建立在RREQ分组中包含了两个序列号:源节点序列号和源节点所知道的最新的目的序列号。源节点序列号用于维持到源的反向路由的特性，目的序列号表明了到目的地的最新路由。当RREQ分组从一个源节点转发到不同的目的地时，沿途所经过的节点都要自动建立到源节点的反向路由。节点通过记录收到的第一个RREQ分组的邻居地址来建立反向路由，这些反向路由将会维持一定时间，一该段时间足够RREQ分组在网内转发以及产生的RREP分组返回源节点。当RREQ分组到达了目的节点，目的节点就会产生RREP分组，并利用建立的反向路由来转发RREP。(c)正向路由的建立RREQ分组最终将到达一个节点，该节点可能就是目的节点，或者这个节点有到达目的节点的路由。如果这个中间节点有到达目的的路由项，它就会比较路由项里的目的序列号和RREQ分组里的目的序列号的大小来判断自己已有的路由是否是比较新的。如果RREQ分组里的目的序列号比路由项中的序列号大，则这个中间节点不能使用己有的路由来响应这个RREQ分组，只能是继续广播这个RREQ分组。中间节点只有在路由项中的目的序列号不小于RREQ中的目的序列号时，才能直接对收到的RREQ分组做出响应。如果节点有到目的地的最新路由，而且这个RREQ还没有被处理过，这个节点将会沿着建立的反向路由返回RREP分组。在RREP转发回源节点的过程中，沿着这条路径上的每一个.节点都将建立到目的节点的同向路由，也就是记录下RREP是从哪一个邻居节点来的地址，然后更新有关源和目的路由的定时器信息以及记录下RREP中目的节点的最新序列号。对于那些建立了反向路由，但RREP分组并没有经过的节点，它们中建立的反向路由将会在一定时间(Active-Route-Timeout)后自动变为无效。收到RREP分组的节点将会对到某一个源节点的第一个RREP分组进行转发，对于其后收到的到同一个源的RREP分组，只有当后到的RREP分组中包含了更高的目的序列号或虽然有相同的目的序列号但所经过的跳数较少时，节点才一会重新更新路由信息，以及把这个RREP分组转发出去。这种方法有效地抑制了向源节点转发的RREP分组数，而且确保了最新及最快的路由信息。源节点将在收到第一个RREP分组后，就开始向目的节点发送数据分组。如果以后源节点了解到的更新的路由，它就会更新自己的路由信息。3、AODV路由表的管理节点的路由中除了存储源和目的节点的序列号外，还存储了其他有用的信息，这些信息成为有关路由项的软状态。与反向路由相关的是路由请求定时器，这些定时器的目的是清除一定时间内没有使用的反向路由项。定时器的设置依赖于自组网的规模大小，与路由表相联系的另外一个重要的参数是路由缓存时间，即在超过这个时间之后，对应的路由表就变为无效。此外，在每一个路由表中，还要记录本节点用于转发分组的活跃邻居。如果节点在最近一次活跃期间(Active-Timeout)发起或转发了到某个目的节点的分组，那么就可以称这个节点为活跃节点。这样，当到达某一个目的节点的链路有问题时，所有与这条链路有关的活跃节点都可以被通知到。一个路由表还有活跃邻居在使用，就可以认为是有效的。通过各个活跃路由项所建立的源节点到目的节点的路径，也就是一条活跃路径。路由表中的目的节点序列号，正如在DSDV路由协议中所使用的那样，可以在无序分组的传送和节点高度移动的极端条件下避免路由环路的产生。移动节点为每一个相关的目的节点维护了一个路由表。每一个路由表包含以下一些信息:目的地址、下一跳地址、跳数、目的序列号及路由项的生存时间。路由表在每一次被用来传送一个分组时，它的生存时间都要重新开始计算，也就是用当前时间加上Aetive-Route-Timeout。如果一个移动节点被提供了到达某一个目的节点的新路由，那么它就会把这个新路由的目的序列号与自己路由表中己有的目的序列号做比较，并将目的序列号大的作为到达目的节点的路由表。如果目的序列号相同，则采用到目的节点所经过的节点数(跳数)最少的那个路由。4、AODV路由维护如果节点的移动不是沿着活跃路径进行的，那么就不会影响己经建立的路由。如果一个源节点在活跃路径上移动，它就要向目的节点重新发起一次路由发现过程。如果移动的节点是中间节点或目的节点，那么一个特殊的RREP分组将转发到那些受移动影响的源节点。周期性发送的Hello分组可以用来确保链路的对称性，并检测不能用的链路。如果不用Hello分组，也可以采用链路层通告机制来报告链路的无效性，这样可以减少延迟。此外，节点在尝试向下一跳节点转发分组失败后，也能检测出链路的不可用性。一旦一个节点的下一跳节点变得不可达，这时它就要向利用该损坏链路的活跃上游节点发送未被请求的RREP（RERR）分组，这个RREP(RERR)分组带有一个新的序列号(即在目的序列号上加1)，并将跳数值设置为二。收到这个RREP(RERR)分组的节点再依次将RREP(RERR)分组转发到它们各自的活跃邻居，这个过程持续到所有的与损坏链路有关的活跃节点都被通知到为止。源节点在收到断链的通知后，如果它还要与目的节点联系，它就需要再次发起新的路由发现过程。这时，它将会广播一个RREQ分组，这个RREQ分组中的目的序列号要在源节点已知的最新目的序列号之上加1，以确保那些还不知道目的节点最新位置的中间节点对这个RREQ分组做出响应，从而能保证建立一条新的、有效的路由。5、AODV协议评价。总之，AODV是一种距离矢量路由协议，采用的算法克服了以前提出的一些算法(如DSDV)的缺点，具有如下优点：(a)基于传统的距离向量路由机制，思路简单、易懂。(b)支持中间节点应答，能使源节点快速获得路由，有效减少了广播数，但存在过时路由问题。(c)节点只存储需要的路由，减少了内存的需求和不必要的复制。(d)快速响应活跃路径上断链。(e)通过使用目的序列号来避免路由环路，解决了传统的基于距离向量路由协议存在的无限计数问题。(f)具有网络的可扩充性。(g)需要周期性地广播分组，需要消耗一定的电池能源和网络带宽。与DSDV以及其他持续存储更新路由信息的算法相比，AODV需要相对较长的路由建立时延，不过AODV采取了以下的一些措施来加以改善：(a)到某个目的节点的路由可以由知道路由的中间节点进行响应。(b)链路失效能够被立即报告，这样路由可重新建立。(c)不活跃的路由在一定时间后会被删除。【实验过程】1、使用cbrgen产生traffic pattern。这个实验由100个无线结点组成，仿真时间为100s，pause time设为100s，暂停时间为0s。设置使用CBR流，最大联机数目为10条，每一条每秒送出10个封包。进入cbrgen工具所在的目录：cd ns-allinone-2.35/ns-2.35/indep-utils/cmu-scen-gen使用cbrgen产生tracffic pattern：ns cbrgen.tcl -type cbr -nn 100 -seed 1 -mc 10 -rate 10.0cbr_n100_m10_r10.tcl这样就在cmu-scen-gen文件夹下面产生了一个cbr_n100_m10_r10.tcl的新文件。将其复制到我们需要进行实验的文件夹中。2、使用sedest产生仿真所需要的结点移动场景。这个实验由100个无线结点组成，仿真时间为100s，pause time设为100s，暂停时间为0s。设置使用CBR流，最大联机数目为10条，每一条每秒送出10个封包。进入工具所在的目录：cd ns-allinone-2.35/ns-2.35/indep-utils/cmu-scen-gen/setdest使用setdest产生移动场景：./setdest -n 100 -p 0.0 -M 10.0 -t 100 -x 500 -y 500 scen_100n_0p_10M_100t_500_500将新产生的文件scen_100n_0p_10M_100t_500_500复制到我们需要进行实验的文件夹中。3、修改TCL程序代码。proc getopt argc argv global opt lappend optlist nn for set i 0 $i $argc incr i set opt($i) lindex $argv $igetopt $argc $argvset opt(chan) Channel/WirelessChannel set opt(prop)Propagation/TwoRayGroundset opt(netif)Phy/WirelessPhyset opt(mac)Mac/802_11if $opt(0)=DSR set opt(ifq) CMUPriQueue else set opt(ifq) Queue/DropTail/PriQueue ;# interface queue typeset opt(ll)LLset opt(ant) Antenna/OmniAntennaset opt(x)500 set opt(y)500 set opt(ifqlen)2000 set opt(seed)0.0set opt(tr)trace1.tr ;# trace fileset opt(adhocRouting) $opt(0)set opt(nn) 100 set opt(cp)cbr_n100_m10_r10 set opt(sc)scen_100n_0p_10M_100t_500_500 set opt(stop)100.0Mac/802_11 set CWMin_ 31Mac/802_11 set CWMax_ 1023Mac/802_11 set SlotTime_ 0.000020 ;# 20usMac/802_11 set SIFS_ 0.000010 ;# 10usMac/802_11 set PreambleLength_ 144 ;# 144 bitMac/802_11 set PreambleDataRate_ 1.0e6 ;# 1MbpsMac/802_11 set PLCPHeaderLength_ 48 ;# 48 bitsMac/802_11 set PLCPDataRate_ 1.0e6 ;# 1MbpsMac/802_11 set RTSThreshold_ 3000 ;# bytes Disable RTS/CTSMac/802_11 set ShortRetryLimit_ 7 ;# retrans_missions_Mac/802_11 set LongRetryLimit_ 4 ;# retrans_missions_Mac/802_11 set dataRate_ 2Mb;# 802.11 data trans_mission rateMac/802_11 set basicRate_ 1Mb ;# 802.11 basic trans_mission rate set ns_new Simulator#打开Trace文件set namfd open ns.nam w$ns_ namtrace-all-wireless $namfd 500 500set tracefd open $opt(tr) w$ns_ trace-all $tracefdset wtoponew Topographyset tracefdopen $opt(tr) w$ns_ trace-all $tracefd#$ns_ use-newtrace $wtopo load_flatgrid $opt(x) $opt(y)set god_ create-god $opt(nn)set chan_1_ new $opt(chan)$ns_ node-config -adhocRouting $opt(adhocRouting) -llType $opt(ll) -macType $opt(mac) -ifqType $opt(ifq) -ifqLen $opt(ifqlen) -antType $opt(ant) -propType $opt(prop) -phyType $opt(netif) -channel $chan_1_ -topoInstance $wtopo -agentTrace ON -routerTrace ON -macTrace OFF for set i 0 $i $opt(nn) incr i set node_($i) $ns_ node$node_($i) random-motion 0puts Loading connection pattern.source $opt(cp) puts Loading scenario file.source $opt(sc)for set i 0 $i $opt(nn) incr i $ns_ initial_node_pos $node_($i) 20for set i 0 $i highest_packet_id) highest_packet_id = packet_id; if(start_timepacket_id = 0) start_timepacket_id = time; if (action =r & trace= AGT & type= cbr) if(first=0) first_received_time= time; first=1; receives+;end_timepacket_id = time; else end_timepacket_id = -1; END for (packet_id = 0; packet_id 0) end_to_end_delay += packet_duration; avg_end_to_end_delay = end_to_end_delay / (receives); pdfraction = (receives/sends)*100; printf( Total packet sends: %d n, sends); printf( Total packet receives: %d n, receives); printf( Packet delivery fraction: %s n, pdfraction); printf( Average End-to-End delay:%f s n , avg_end_to_end_delay); printf( first packet received time:%f sn, first_received_time); 将该awk文件lab5.awk放到我们的实验文件夹下。至此，我们的实验文件目录下总共有下列文件：scen_100n_0p_10M_100t_500_500、 cbr_n100_m10_r10、lab5.tcl、lab5.awk。4、运行tcl程序及awk程序。进入到我们的实验文件目录：cd nslab/lab5运行lab5.tcl文件：ns lab5.tcl AODV 利用gawk工具分析trace1.tr文件。至此我们的实验目录下生成了trace.tr文件。我们用gawk工具对其进行分析。终端输入：awk -f lab5.awk trace1.tr 运行结果显示了AODV协议下分组投递率、平均端到端时延等参数。【实验结果】执行该Tcl脚本，生成的Trace文件应该类似下图： trace文件中可以看到aodv标志的包。