组网协议（精选7篇）
组网协议 篇1
当前广泛应用的网络 (如GSM、CDMA等) 均需固定的网络基础设施支持。移动自组网 (Mobile Ad Hoc Network, MANET) 是一种与上述通信类型不同的无线网络。是一个多跳的临时性无中心网络, 由一组带有无线收发装置的移动节点组成, 该网络能够随时随地快速搭建, 且无需网络基础设施的支持。其具有特点如下[1]: (1) 拓扑结构动态变化。由于网络节点的自由移动、随时开关机以及收发装置功率的变化等, 各节点间通过无线信道形成的网络拓扑结构也可能随时发生变化, 且不可预测。 (2) 自组织性。该网络没有中心, 所有节点可自由移动, 地位平等, 是一个对等式网络。所有节点都可以随时加入或离开网络, 任何节点的故障均不会影响整个网络的运行。 (3) 多跳组网方式。网络中的节点除了具有普通移动终端所需的功能外, 还具有报文转发能力。当通信的源节点和目的节点相距较远, 不在直接通信的范围内时, 可借助中间节点通过转发报文进行通信。
1 MANET与传统无线网络在路由上的区别
目前生活中常见的移动通信网络主要有蜂窝数据网络和无线局域网, 在系统的组织、管理和维护方面都与MANET有较大的区别[2]。
1.1 MANET与蜂窝数据网络的区别
典型的蜂窝数据网有全球移动通信 (Globa System for Mobile communication, GSM) 网络和码分多址 (Code Division Multiple Access, CDMA) 网络, 网络中的移动节点主要通过基站进行连接, 基站之间通过有线网络进行互联, 因此移动节点之间通信路由的建立或选择主要由基站等固定基础设施完成。而在MANET中, 不存在固定基础设施, 节点通信路由的选择和建立完全由移动节点完成。在蜂窝数据网中, 由于有网络固定基础设施的存在, 网络结构相对较为稳定。而在MANET中, 节点的随意移动会使得网络拓扑结构动态变化, 影响通信路由的选择。
1.2 MANET与无线局域网的区别
无线局域网中的节点通过无线接入点连接到网络, 是单跳的网络, 路由器和主机通常是两个独立的设备。而MANET是多跳的网络, 每个节点均同时具备路由和主机两种功能。通过比较发现, MANET与传统的无线网络在路由方面有较大差异, 因此路由协议是MANET研究的重点内容。
2 MANET路由协议分类
MANET的路由协议可基于不同角度进行分类[1,3], 如按路径类型可分为单路径型路由协议和多路径型路由协议, 按广播方式可分为单播路由协议和多播路由协议, 按地理定位方式可分为地理定位辅助路由协议和非地理定位辅助路由协议, 而最常见的分类方式有以下两种: (1) 按网络拓扑结构分类。从这个角度可分为平面结构和分层结构两种。对于前者, 所有移动节点地位平等, 如动态源路由协议 (Dynamic Source Routing, DSR) 。对于后者, 网络中的所有节点按簇划分, 每个簇由一个簇头和若干个簇成员组成, 多个簇头又是更高一级簇的成员。 (2) 按驱动方式分类。可分为表驱动和按需驱动两种, 例如图1所示。前者采用周期性的路由分组广播来交换路由信息, 如目的序号距离矢量路由协议 (DSDV) ;后者则是根据发送数据分组需要进行路由发现, 建立路径, 实现信息传送。如需求驱动距离矢量路由协议 (Ad Hoc Ondemand Distance Vector, AODV) 和临时排序路由选择算法 (Temporary Ordered Routing Algorithm, TORA) 协议。
3 典型的MANET路由协议
文中选取DSDV作为表驱动路由协议的代表重点介绍;选取AODV、DSR作为按需路由协议的代表并作重点介绍。
3.1 DSDV协议
DSDV是一种基于距离矢量算法的路由协议[4], 通过附加序列号的方法来区分路由的新旧程度, 进而防止可能产生的路由环路。 (1) 路由表结构。每个节点包含一个路由表, 路由表项包括:目的信宿、下一跳、度量值和序列号。 (2) 信息通告。各个节点周期性地向邻居节点通告其当前的路由表。 (3) 链路断开。如果在较长一段时间内无法收到邻居节点的广播消息, 可推断出链路断开, 同时, MAC层实体也可检测到。一旦链路断开, 则通过以下方法通知网络中其余节点:1) 断开的链路度量值为∞。2) 节点检测路由表, 下一跳经过该链路的路由表项的度量值标记为∞, 并分配一个新的序列号, 且为奇数, 以区别于信宿发出的更新报文。3) 触发“递增更新”报文的立即发送。经过以上过程, 在较短时间内, 该链路的变化将通告到网络的各个节点。 (4) 路由选择准则。DSDV中路由选择的准则为:序列号新或度量值小。
DSDV协议操作实例:在图2及表1表2中, MHi (i=1, 2, …, 8) 表示节点标识, SXXX_MHi (i=1, 2, …, 8) 发出更新报文的序列号为XXX。以MH2为例, 当MH1移动, 成为MH7的邻居时, MH1与MH3的链路断开。表1和表2分别为MH1移动前和移动后MH2的路由。
3.2 AODV协议
AODV路由协议[5]是按需驱动的距离矢量路由协议, 使用目的序列号和经典的距离矢量算法, 具有对动态链路的快速自适应, 处理和存储开销小, 网络利用率小等优点。AODV路由协议最明显的特征是每条路由均使用一个目的节点序列号, 能够确保路由是开环的。该序列号由目的节点产生, 与发送给路由请求节点的信息相组合。协议由两部分组成:路由请求和路由维护。
AODV的路由请求 (RREQ) 包含下列项[6]:
<跳数;路由请求码;目的地址;目的序列号;源地址;源序列号>
收到请求报文的节点, 查看路由表中是否有到目的节点更新的路由, 即目的序列号大于等于请求报文中的序列号。若没有, 该节点将记录请求报文的信息并广播;若有或节点是目的节点, 则将发送路由应答报文 (RREP) 给源节点。RREP包含如下项:
<跳数;目的地址;目的序列号;源地址;寿命>
转发RREP的节点根据RREP更新路由表, 并将RREP转发给先前记录的上游节点, 直至源节点S, 此时由源节点到目的节点的路由已建立。
AODV通过周期性的广播Hello报文来监视链路状态[7], 若节点在使用过程中发现某条链路断开, 则将从自身的路由表中删除包含该链路的路由, 并发送“路由出错”报文 (RERR) 给因链路断开而不可达的节点, 沿途转发RERR的节点并同时删除自身路由表中的对应路由。如图3所示, 节点6为目的节点, 由于节点4从4处移动到4'处, 导致节点3到目标节点的链路中断。图3 (a) 所示为RERR通知过程, 图3 (b) 所示为重新建立的路由。
3.3 DSR协议
DSR是动态源路由协议[7,8], 其最重要的特点是利用了源路由, 即发送方知道到达目的地的完整路径, 可实现节点间跨越多跳传输空间进行通信。DSR路由协议包括路由寻找和路由维护两个主要机制, 共同作用于移动Ad Hoc网络, 完成源路由的寻找和维护。
(1) 路由寻找。当节点S有分组要发送至节点D, 而S并未找到任何可用的路由, 那么节点S就通过路由寻找协议来动态的寻找一条可达节点D的新路由。如图4所示, 源节点S试图寻找一条路由到达目的节点D。
节点S的路由寻找进程执行如下:1) 节点S按照本地广播分组方式发送路由请求 (RREQ) , 被当前正处在节点S的无线电波覆盖范围的所有节点所接受, 如节点A。RREQ识别路由寻找的源节点和目的节点, 也包含了由源节点确定的唯一请求识别码 (Request ID) 。RREQ还包含一个记录列表, 用于记录该RREQ被成功转发的中间节点。2) 当另一个节点接收到该RREQ时, 若该节点是目标节点, 则给源节点回送一个路由应答 (RREP) , 同时回送在路由寻找过程中的路由记录, 源节点接受到该RREP后, 存储该路信息。否则, 若接受到该RREQ的节点已经收到另一个来自相同源节点、具有相同请求识别码和目标节点的RREQ, 或该节点已经发现自己的地址已在该RREQ的路由记录中, 那么该节点认为该路由请求已被接受, 即丢掉该路由请求;否则该节点将自己的地址添加到该RREQ的记录中, 然后按照本地广播分组方式将该路由请求发送出去。3) 目的节点D收到RREQ后, 要给源节点S回送路由应答 (RREP) , 先检查自己是否有到达源节点S的路由, 如果有, 则目的节点D通过这条路由将RREP交付给源节点S;否则, 目的节点D执行自己的路由寻找, 找出到达源节点S的路由。
(2) 路由维护。当使用某条源路由发送分组时, 该路由中的节点均要通过应答 (Acknowledgement) 机制来保证该分组能够顺利到达下一跳节点。若一个应答请求发送后仍未得到回应, 则需要重发, 当重发次数达到最大值时, 发送节点则认为到下一节点的链路已经断开, 同时从路由表中删除该断开链路, 并给该源路由上的节点回传一个路由错误 (Router Error) 。
如图5所示, 若节点B经过若干次应答请求后, 仍未接收到节点C的回应, 则B认为到C的链已断开, 同时从路由表中删除该断开链路, 并给S及所有同样的节点回传一个路由错误。若S的路由表中存在另一条到达D的路由, 则S使用该条路由, 否则S应执行一个新的路由寻找来获取一条可到达D的新路由。
4 MANET路由协议发展方向
目前, MANET路由协议的研究多集中在设计路由协议, 用来支持网络节点之间的高效通信。MANET路由协议的性能和多样性仍有较大的提高空间, 其中包括以下几个方面: (1) 路由安全性。MANET与传统网络结构上的差异导致传统网络中的安全机制不再适用于MANET。对于MANET来说, 路由安全具有重要的地位, 也是较难解决的问题。路由协议是网络攻击的主要目标, 然而目前已经提出的路由协议在安全方面鲜有涉及, 因此提高路由协议的安全是今后的研究方向。 (2) 路由协议的节能问题[9]。由于MANET没有固定基础设施的支持, 单个节点必须依靠可携带的电源提供能量。网络的发展导致单个节点的能量消耗越来越大, 这就使得减少节点的耗能显得尤为重要。目前的许多协议都没有节能策略, 因此这方面的问题仍有待进一步的研究。
参考文献
[1]张程.移动自组网的关键技术研究[D].重庆:重庆大学, 2010.
[2]陈林星.移动Ad Hoc网络-自组织分组无线网络技术[M].北京:电子工业出版社, 2006.
[3]李振宇.移动自组网中路由协议的分析与研究[D].北京:北京邮电大学, 2006.
[4]AMITH K.Step by step procedural comparison of DSR, AODV and DSDV Routing protocol[C].Torolento:ICCET, 2012.
[5]吴翠萍, 蔡明.AODV路由协议的改进[J].计算机工程与应用, 2012, 48 (24) :91-94.
[6]SARITA R, SINGH B, BHADAURIA W, et al.Bandwidth reservation routing technique based on agent in mobile ad hoc networks using rate control with AODV[C].Amsterdam:ICNCS, 2012.
[7]KHATAWKAR S D, PANDYAJI K K.Performance comparison of DSDV, AODV, DSR routing protocols for MANETs[C].Paris:ICCNC, 2012.
[8]SANGEETA B, SUNEETA M.Study of DSR routing protocol in mobile adhoc network[C].Nanjing:ICINT, 2011.
[9]李鹏.基于能量的移动自组网路由协议研究[D].武汉:华中科技大学, 2006.
无线自组网中的路由协议 篇2
Ad Hoc网络自身的特殊性决定了路由协议的特殊性和重要性,动态变化的网络拓扑结构要求路由必须建立及时迅速,有限的无线网络资源要求路由协议必须具有较小的开销和能耗。传统的路由技术已无法适应Ad Hoc网络动态变化的拓扑结构,必须设计新的适合Ad Hoc网络特点的路由协议。
目前,国内外许多相关的大学和科研机构都开始了Ad Hoc网络特别是Ad Hoc路由技术的研究。上个世纪九十年代中后期,各研究机构向MANET工作组提交了许多路由选择协议[2],如卡耐基马龙大学提交的动态源路由DSR[3],C-K。Toh提交的ABR[4]等。这些路由协议各自基于不同的出发点和度量,通过按需机制解决了动态变化的拓扑结构带来的问题。从路由路径上分,目前的Ad Hoc网络按通信模型分可分为单径路由和多径路由两大类,下面分别予以介绍。
1 单径路由
传统的分类方法将Ad Hoc网络中的路由分成“表驱动”和“按需驱动”两大类,表驱动路由中,网络中的任一节点都维护一个到其它所有节点的路由表。当网络拓扑发生变化时,节点间及时更新该信息以维护路由表的正确性。按需驱动路由中,仅当源节点有路由需求时才启动路由发现,针对特定的目的节点在网络中找到合适的路径。在该路径的使用中,网络中的相关节点会通过消息的交互来维护有效的路由并删除失效的路由多径路由是指在同一对源/目通信节点之间建立多条不相交的路径同时进行分组投递,源节点和目的节点对之间的多条路径能够补偿移动Ad Hoc网络的动态特性和不可预测性,从而改善通信双方的通信服务质量[5]。
这种传统分类方法过于模糊,还可以根据Ad Hoc的网络结构将路由协议分为平面路由协议和分级路由协议。平面路由协议在网络中没有等级的划分,所有的网络节点都具有同样的功能与优先级,它们以相同的动作收发路由控制信息。而分级路由协议在处理路由信息时需要区分级别不同的节点以减少控制报文的数量。分级路由协议又分为两种,一种称为邻居选择,该协议中的节点根据其邻居节点动态选择路由;另一类称为分区选择,即根据网络拓扑划分区间进行管理。
根据Ad Hoc网络的状态信息可将路由协议分为基于拓扑和基于目的节点的路由协议。基于拓扑的路由协议需要在节点保存大量拓扑信息,这与链路状态协议的原则是一致的。基于目的节点的路由协议在节点不需要保存大量拓扑信息,只需要保存所需的最近节点的拓扑信息,这类协议中最著名的是距离矢量路由协议,该协议需要维护到达目的节点的距离矢量。
此外,根据路由建立方式可以分为先应式路由协议和被动式路由协议。先应式路由协议以表驱动路由协议为代表,每个网络节点为目的节点保存路由信息,所有的节点周期性地交换路由信息。被动式路由协议的过程可分为路径发现和路由保持,路径发现只有在源节点有需求时才会启动,路由保持则是在拓扑信息发生变化时寻找丢失的路由信息并重新启动路径发现。
2 多径路由
多路径传输(Multiple Path Transport:MPT)是指采用多条不相交的路径来投递应用分组,以增加连接的带宽和可靠性的机制。移动Ad hoc网络中,由于缺乏基础设施、网络拓扑动态变化等,其对QoS的支持较弱。但是其网络结构和用户的移动增加了网络的灵活性、用户的多样性和网络的容量,这些都对在其中实施MPT提供了有利的因素。
多路径路由模型为任意一对节点同时提供多条可用路径,并允许节点主机(或应用程序)选择如何使用这些路径。多路径路由算法为节点间提供多条路径,并确保发往其中一条路径的数据经由该路径到达目的地。为在节点间计算路径,必须根据路径的用途规定路径的特性。如为了得到最大的端到端吞吐量,必须规定路径的特性是:在任意节点对之间的多条路径的聚合吞吐量最大。而为了得到最小的端到端时延,就必须规定路径的特性是:任何时刻,任意节点对之间都存在至少一条具有最小时延的路径。路径规格规定了特定路径集合的特征,路径计算算法实际计算出符合路径规格所规定的特征的路径集。
路径类型规定了节点对间的多条路径之间的关系。有两种路径类型:多服务的多路径和多选择的多路径。多服务的多路径是具有不同特征的多条路径。例如,网络可以同时提供高带宽路径和低时延路径,这使得应用程序可以选择最符合其通讯要求的路径。多选择的多路径为同一服务提供多条路径。例如,网络可能为高带宽服务提供四条路径,即每个节点都有到任意目的节点的四条高带宽路径。但一般说来多服务的多路径选择算法一般较为复杂,不易实现,而多选择的多路径选择算法相对容易,故目前一般多采用多选择的多路径路由。
3 多径路由的使用模式
对多路径的使用模式,主要有两种:在同一时刻对于每个源节点-目的节点对只能在某条路径上传输数据,当这条路径中断时,可以用多条路径中的其它路径(备份路径)来传输,该模式称之为“备份多路径”;另一类是对每个源节点-目的节点对能够同时使用两条或两条以上的路径来传输数据,该模式称之为“并行多路径”。
4 多径路由的优势
1)容错多路径传输可以避免传统的单路径路由中路由错误后的重新路由过程。
如图1所示,源节点S与目的节点D间有三条路径,如果S同时沿着三条路径向D发送同样的数据包,那么只要三条路径中有一条路径正常工作,数据包就能到达D。图中节点D由于移动,原先的两条路径S-A-D和S-B-D都相继失效,只剩下S-C-D,但此时S和D仍能够正常地通信,需要注意的是这期间并没有重新路由的过程。但如果采用传统的单路径路由,原先有可能选中最短路径-S-B-D,但当D移动,B-D之间的链路出现错误后,就需要重新路由找到路径S-C-D,而后再进行传输。这期间就有重新路由的过程,即S和D之间就有一段时间不能正常通信。当然像这种在所有路径上发送同样数据包的冗余数据的做法,并不是最好或唯一的利用多路径的方法,这里只是利用它来说明多路径路由是如何在链路出现错误的时候提供错误容忍服务的。
2)高带宽无线网络中的带宽比有线网络要低很多,为一个连接建立的单独的一条路径可能不能提供满足需求的带宽。然而如果使用多条路径同时传送数据(当然不是像上述的不同路径上传送相同的数据),就能够取得满足要求的带宽。同时,因为有更多的带宽可以获得,就可以取得更小的端到端的延时。
5 多径路由协议
好的路由协议可以进一步增强多路径的性能,多路径集合的选择要根据诸如路径特征、链路层上的相互影响等标准进行。从错误容忍的角度来看,更多“健壮”的路径应当被选择以减小路径出错的几率。目前常见的Ad Hoc网络中的多径路由协议有SMR协议[6]和AOMDV协议[7]。
6 结束语
根据本文的分析介绍,可以看出,多径路由技术由于具有容错性好,带宽高等优势,非常适合在Ad Hoc网络中应用,将使未来移动Ad Hoc网络路由的主要方式,但目前,对移动Ad Hoc网络多径路由技术的研究仍然处于初级阶段,还有许多诸如路由发现、路由选择策略等问题需要进一步深入研究。
摘要：无线自组网组网方式灵活,整体鲁棒性高,系统成本低,近年来引起广泛关注。在无线自组网中,路由协议占有重要地位,该文分析了无线自组网中的路由协议,重点介绍了多径路由技术。
关键词：Ad Hoc,无线自组网,多径路由
参考文献
[1]Corson MS,Macker J R,Cirincione G H.Internet-Based Mobile Ad Hoc Networking[J].IEEE Internet Computing,1999,3(4):63-70.
[2]Royer E M,Toh C K.A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks[J].IEEE Personal Communica-tions,1999,6(2):46-55.
[3]Johnson D B,Maltz D A,Broch J.The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks[Z].Internet Draft,MANETWorking Group,draft-ietf-manet-dsr-01.txt,1998.
[4]Toh C K.A Novel Distributed Routing Protocol To Support Ad-Hoc Mobile Computing[C].Proc.1996 IEEE 15th Annual Int’l.Phoenix Conf.Comp.and Commun.,1996:480-486.
[5]Kuosmanen R.Classification of Ad Hoc Routing Protocols[EB/OL].http://eia.udg.es/～ramon/xdsi_ant/classification-of-ad-hoc.pdf.
[6]Lee S J,Gerla M.Split multi path routing with maximally disjoint paths in Ad Hoc networks[J].ICC’01.June 2001,10:3201-3205.
组网协议 篇3
由于航空自组网具有动态拓扑、有限带宽、多跳路由、自组织、存在单向信道等特点,对在其上运行的路由协议便提出了许多具体而严格的要求。因此,路由协议的设计和选取一直是航空自组网中的重点和难点。
1 航空自组网中的路由协议
在航空自组网中,由于节点的高速移动导致拓扑结构动态、随机且快速地变化,这样常规路由协议在拓扑结构变化时,就会花很大代价重新使路由收敛,占用大量的网络资源,致使信息的传输无法实现。目前,典型的航空自组网路由协议以目的节点序列距离矢量(Destination Sequence Distance Vecto,DSDV)和按需距离矢量(Ad Hoc on Demand Distance Vector,AODV)路由协议为代表,特别是伴随着卫星定位系统的发展,基于地理信息的栅格路由协议(Grid Routing Protocol,GRID)也越来越受亲睐。
相关文献已经研究了多种适应于航空通信环境中的路由协议,但对这些协议的性能分析和比较还不够全面。文献[3,4]指出AODV等按需路由协议应用于航空自组网会出现路由发现的时延较大,文献[5]仿真表明DS-DV等先验路由协议会产生大量的网络开销,而且收敛速度慢。文献[6]提出的GRID路由协议可以避免路由探测分组的盲目洪泛广播,进行有效的路由发现和路由维护。但这些文献研究重点都放在了比较各路由算法本身在网络中所占用的开销,而没有深入研究不同路由协议对业务的影响。
本文重点研究了DSDV、AODV和GRID对网络性能的影响,采用路由开销、端到端平均延时、分组丢失率和平均跳数这4个指标作为衡量网络性能的标准。
2 路由协议描述
2.1 DSDV路由协议
DSDV路由协议[7]是一种主动路由协议,维护的路由表采用触发式的更新机制,并且会根据触发机制周期性地在网络中进行广播和更新。其基本思想是在传统Distance-Vector算法的基础上采用序列号机制,给每个路由设定序列号来区分新旧路由,网络中的每一个节点维护一个路由表,路由表中记录着到达网络中所有节点的路由信息,比如路由路经、目的节点序列号和到达目的节点的跳速。其中,目的节点序列号用于区别有效和过期的路由信息,从而避免了失效路由和环路的产生。
DSDV路由表的更新策略是周期性的,所以每个节点的路由表会周期性地进行更新,这种更新对于网络拓扑结构的变化是有利的,而且路由表更新频率会伴随着网络拓扑结构的变化而进行调整,从而保证路由的时效性。
2.2 AODV路由协议
AODV路由协议[8]是一个纯粹的按需路由系统,不在路径内的节点不保存路由信息,也不参与路由表的交换。AODV路由协议可以实现在移动终端间动态、自发地路由,使移动终端很快获得通向所需目的地的路由,同时又不用维护当前没有使用的路由信息,并且还能很快对断链的拓扑变化作出反应。
AODV的操作是无环路的,在避免了通常Bellmanford路由算法的无穷计数问题的同时,还提供了很快的收敛速度。AODV的路由表中每项都使用了目的节点序列号,该序列号是目的节点创建并在发给源节点的路由信息中使用的,使用目的节点序列号可以避免路由环路的发生。
2.3 GRID路由协议
GRID路由协议[9,10]是基于地理信息的完全感知型路由协议,其基本原理是网络中的每一个节点都配有一个可以对自身地理位置和移动状态进行精确定位和测量的装置,如GPS,在数据传输之前,源节点通过定位装置确定目的节点的地理位置并将该位置信息写入数据包的头部,然后数据包会根据目的节点的位置信息选择合适的路径进行数据转发直至该目的节点。
GRID路由协议把整个网络划分为若干个等边虚拟栅格,在每一个栅格中通过一定的策略选取一个节点担当网关,负责通过所在栅格内所有数据包的转发工作。
3 路由连通性能评估准则
3.1 路由开销
路由开销是指节点发送的用来进行路由查询或路由维护等目的的控制报文数。在逐跳的路由查询过程中,对于每一跳所转发的路由报文都需要计算在这个开销之内,路由开销反映了一个路由协议是否具有可扩展性。在主动路由协议(如DSDV)中,主要的路由开销是由节点位置广播造成的更新开销(Location-Update-Overhead,LUO),而在按需路由协议(如AODV)和地理路由协议(如GRID)中,主要的路由开销则是由路由发现引起的搜索开销(Rout-Search-Overhead,RSO),LUO伴随着节点位置更新广播频率的增大而不断增加,同时,这种节点位置更新广播频率的增大也降低了用于路由发现的搜索范围,即随着节点位置更新广播频率的增大,RSO是一个递减的过程,所以,LUO和RSO在某一个频点A时,会取得相同的值,如图1所示。
而在实际场景中,节点位置更新的广播频率是伴随着网络拓扑结构的变化而变化的,所以,网络拓扑结构的变化会影响路由开销,例如,网络中移动节点的运动情况、网络中节点的分布情况都会对路由开销造成影响。具体的,路由开销可表示为
式中:RSO表示搜索开销;LUO表示更新开销。即当RSO与LUO之和最小时,路由开销得到极值RCmin。
3.2 端到端平均延时
网络的端到端延时(End-to-End Delay)定义为数据分组从源节点的发起直到被目的节点正确接收所经历的时长。端到端延时反映了网络中业务处理的响应时间,当信道资源缺乏或网络拥塞严重时,传输延时将会增大,因此该性能参数是系统实时性以及拥塞状况的一个重要衡量指标。具体如
式中:D(i)表示第i个分组的传输时延;RT(i)表示第i个分组的接收时间;ST(i)表示第i个分组的发送时间。通常,对式(2)取均值,可以得到端到端平均延时,即
式中:N代表分析脚本中N个分组。进一步通过对不同分组的端到端时延进行统计计算,可以得到时延抖动(Delay-Jitter),时延抖动可以定义为前后两个分组的时延之差,即
而在实际网络中,常对最小时延Dmin和最大时延Dmax进行均值处理,然后用均值时延和这两者进行比较,即
当式(5)所得到的值在允许的阈值之内,那么可以认定网路的时延抖动J较小,网络的稳定性好。
3.3 分组丢失率
分组丢失率(Packet-Loss-Rate)是指网络在转发数据分组的过程中,被丢弃的数据分组个数占源节点发出的数据分组个数的比例。发生分组丢失的原因很多,例如网络拥塞、接收分组的缓冲区不足、TTL值超过门限值以及无线信号的同频干扰等。分组丢失率反映了网络连通性能的效率,当网络发生分组丢失的现象时,数据的传输会受到影响,例如在视频传输过程中出现分组丢失,则会出现马赛克现象。分组丢失率也从一个侧面反映了路由协议的适应性和鲁棒性,具体可表示为
式中:NSP表示节点发送的总的分组数目,NRP表示节点接收到的分组数目。通常分组丢失率也可以用分组投递率PGR来间接表示,即
即分组投递率越大或者分组丢失率越小,网络的连通性能效率越高。
3.4 平均跳数
平均跳数(Mean-Hop)是指从源节点到目的节点,完成一条路由经历所有中继节点的跳数的均值。具体的,平均跳数可以通过两个方面解释:如果侧重网络中数据包分组的发送情况,平均跳数可以定义为分组转发的总次数(Fowd-Packet)与分组总个数(Number of Send Packet)的比值,即
式中:分组总个数NSP包括成功转发的分组个数(Number of Send Packet Success,NSPS)与被丢弃的分组个数(Number of Send Packet Loss,NSPL),为了简化程序,一般忽略被丢弃的分组个数。
同样的,如果侧重网络中拓扑结构的情况,可以直接通过对源节点和目的节点之间路由经历的中继节点的个数进行统计,得到相关跳数的统计均值,即
式中:M表示源节点和目的节点之间存在的链路的个数;N(i)表示第i条链路所经历的中继节点的个数。
平均跳数受到路由协议策略以及节点有效辐射半径的影响,平均跳数的增多会导致网络路由开销的非线性增加,从而间接地造成网络拥塞和分组丢失。
4 仿真及性能分析
仿真软件采用NS2,节点个数设定为50,单跳距离为500 m,移动速度为0～100 m/s,暂停时间设置为10 s,仿真时间为2 000 s。仿真区域大小设为变量,决定节点密度。节点移动模型采用适用于航空环境的RWP模型。路由协议采用AODV路由协议、DSDV路由协议和GRID路由协议,以此来验证按需路由协议、主动路由协议和基于地理信息路由协议在航空自组网环境中的性能。
4.1 路由开销
由图2可以得到,随着网络中节点密度的增大,DS-DV路由协议的路由开销总体呈现出一个先逐渐增大,然后平缓增大的趋势,这是由于节点密度逐渐增大,节点之间的相对位置变化度就会逐渐增大,即路由对节点的运动情况比较敏感,需要对路由表进行频繁更新,所以路由协议会根据路由策略增大节点位置广播的频率,从而进一步使路由开销增大。
在AODV路由协议中,路由开销伴随着节点密度的增大,呈现出一个先增大后减小的过程,而且总体路由开销比DSDV路由协议的开销要高,这首先说明了路由发现过程引起的路由开销要比节点位置广播的更新开销要大,其次说明了在AODV路由协议中,路由发现引起的路由开销并不会因为节点密度的逐渐增大而无限增大,而是在达到一定的程度后开始逐渐降低,这是由于大量的路由发现过程会导致丢包现象的产生。
在GRID路由协议中,路由开销整体呈现出一个较平稳的过程,没有出现路由开销急剧增加和突然减小的情况,这是由于GRID路由协议中,每个栅格网关节点的分布具有一定的概率平稳性,而且由于有限泛洪式的路由发现策略,路由开销不会因节点密度的变化而发生过大的变化。
4.2 端到端平均延时
如图3所示,从整体情况看到AODV路由协议的端到端平均延时最小,DSDV路由协议次之,GRID路由协议最大。这是由于在DSDV路由协议中,数据包的收发过程会选择最短路径和最少跳数的路由,而AODV路由协议和DSDV路由协议具有类似的路由策略,但同时也具备了DSR路由协议的良好路由发现策略,所以端到端平均延时对比有所提升。而GRID路由协议的端到端平均延时有一个逐渐增大随后平缓的过程,这反映出GRID路由协议的端到端平均延时相比较大,但是在高节点密度情况下趋于平稳,即在此情况下,时延抖动较小,网络的稳定性好。
4.3 分组丢失率
如图4所示,分组投递率都伴随着节点密度的增加,呈现出一个递增趋势,并且在节点密度到达一定值时趋于稳定,这说明了节点密度越大,节点间建链的概率越大,但是在节点密度逐渐变化的过程中,DSDV路由协议、AODV路由协议的分组投递率变化程度较大,说明这两种路由协议的分组投递率对于节点密度的变化比较敏感,路由协议的连通适应性和鲁棒性不佳;而GRID路由协议虽然也有变化,但是整体变化度不大,而且基本维持在一个比较好的数值范围内,所以得到GRID路由协议在分组投递率方面有优势。
4.4 平均跳数
伴随着节点密度的逐渐增加,DSDV路由协议、AODV路由协议和GRID路由协议的平均跳数都呈现出一个比较稳定的情况,如图5所示,DSDV路由协议的平均跳数最小,这主要是由于路由策略中路由寻求最短路径的本质特性而导致。AODV路由协议的平均跳数比DSDV路由协议的平均跳数稍大,这是由于AODV路由协议是在DSDV路由协议的基础上进行了路由策略的改进和提升。而GRID路由协议的平均跳数明显比以上两种路由协议的平均跳数要大,而且在某一个节点密度的情况下出现了一个比较明显的拐点,一方面说明了GRID路由协议必须要通过网关节点进行数据中继转发,会造成过多的跳数,另一方面也说明了节点密度发生的变化可以等效为栅格的尺寸划分变化,而且,在某一个特定的节点密度下,平均跳数会出现一个极值。
5 小结
本文通过NS2对AODV路由协议、DSDV路由协议和GRID路由协议进行仿真,并定义了4个准则,从这4个准则角度分析评价了这3种协议在航空自组网中的性能。得出的结论是,在航空自组网环境中,不同的路由协议性能和侧重点不同,所以在进行航空自组网的研究中,选择具有特定优势的路由协议以符合特定的应用需求至关重要。
参考文献
[1]徐雪飞,甘忠辉,刘芸江.基于地理信息的航空自组网路由协议综述[J].电讯技术,2011,51(5):133-138.
[2]SAKHAEE E,JAMALIPOUR A,KATO N.Aeronautical Ad Hoc net works[C]//Proc.IEEE WCNC.Las Vegas,USA:IEEE Press,2006:246-251.
[3]JOHNSON D B,MALTZ D A.Dynamic source routing in Ad Hocwireless networks[M].[S.l.]:Kluwer Publishing Company,1996.
[4]ROYER C E,DAS S R.Ad hoc on demand distance vector routing[C]//Proc.2nd IEEE Workshop on mobile Computing Systems andApplications.USA:IEEE Press,1999:90-100.
[5]PERKINS C E,BHAGWAT P.Highly dynamic destination se quenced distance vector routing(DSDV)for mobile computers[C]//Proc.ACM SIGCOMM Conference.USA:IEEE Press,1994:234-244.
[6]LIAO Wenhwa,SHEN Jangping.GRID:a fully location-aware rout ing protocol for mobile Ad Hoc networks[J].Telecommunication Sys tems,2001(18):61-84.
[7]TIAN D,SHAFIEE K,LEUNG V C M,et al.Position-based direc tional vehicular routing[C]//Proc.GLOBECOM.[S.l.]:IEEE Press,2009:1-6.
[8]BAKHOUYA M,COTTIN N.Performance evaluation of the location-based protocol DREAM for large mobile Ad hoc networks[C]//Proc.New Technologies,Mobility and Security.[S.l.]:IEEE Press,2008:1-6.
[9]CHAO Chihmin,SHEU Jangping,HU Chengta.Energy-conservinggrid routing protocol in mobile Ad Hoc networks[C]//Proc.Interna tional Conference on Parallel Processing.[S.l.]:IEEE Press,2003:265-272.
组网协议 篇4
关键词：移动自组网,QoS路由,路由协议
0引言
移动自组网又名Ad Hoc网络,是没有任何中心实体的自组织网络,依靠节点间的相互协作在移动、复杂多变的无线环境中自行成网,借助于多跳转发技术来弥补无线设备的有限传输距离、从而拓宽网络的覆盖范围,为用户提供各种服务、传输各种业务。这是一种不需要依赖现有固定通信网络基础设施、 能够迅速展开使用的网络体系,网络节点能够动态地、随意地、 频繁地进入和离开网络。每个节点都兼任终端和路由的角色, 需要完成发现及维护到其它节点路由的工作,因而在这种网络中路由就成为了一个核心问题。
随着移动自组网应用领域的日益壮大,提供端到端的服务质量Qo S也成为了衡量移动自组网的一个重要准则。服务质量 (Quality of Service,Qo S)通常定义为把分组流从源节点传输到目的节点时网络必须满足的一个服务要求集合,期望网络向终端用户提供端到端的服务保证以及基于策略的网络性能的服务属性,例如,时延、时延抖动、带宽、分组丢失率等等,把这种根据网络中可使用资源和业务Qo S需求来选择的路由的机制称为Qo S路由。加入Qo S后能使得移动自组网的应用更加灵活,将传统的最短路径改为一条满足业务Qo S需求路径,不仅能够满足用户端到端Qo S要求,而且还尽可能有效地使用网络, 以最大化网络资源的利用率。
移动自组网由于其自身的灵活、健壮、投资成本低等特性, 现已被广泛应用在多个领域,而移动自组网中的Qo S路由技术, 也成为了一个核心技术和重要研究方向。
1QoS实现的难度
传统的用于固定网络的Qo S路由技术不能直接用于移动自组网中,移动自组网自身具有特殊的属性,如链路干扰、链路传输范围有限、带宽有限、拓扑高度动态变化等等,这使得在移动自组网中提供Qo S服务保证非常困难,主要包括以下难点:
(1)资源有限
移动自组网的无线信道质量不稳定,信道带宽有限。提供Qo S服务保证势必会增加系统开销,为实时获取Qo S状态信息而进行的状态信息扩散不仅会占用带宽,还可能产生过多的冲突从而降低网络性能。只有当采用了Qo S路由后带来的好处大于实现其功能所付出的代价时,才予以考虑是否采用Qo S路由。
(2)链路状态难以确定
相对于有线信道,无线信道属于广播媒介,其参数时变且易受干扰,使得无线链路状态难以确定,如带宽、时延、时延抖动等链路状态参数,难以实时获取和维护。
(3)网络动态变化特性
移动自组网的动态变化性使得节点难以保证其保存的可用状态信息是准确的,并且节点随时随地都能离开或者加入网络, 链路随时都会发生变化,而传统Qo S路由协议则主要依据准确的状态信息进行判断。
(4)多Qo S条件约束
Qo S约束可以是一维的参数,也可以是多维的,将其Qo S路由对应地称作单维和多维Qo S路由。按照性能特征可以将Qo S度量参数划分成三类,即可加性参数、可乘性参数和凹性参数。
对于路径P (i, j,k,......,l,m) ,用d(i, j) 表示链路d(i, j) 的某种Qo S量化参数,用d(i, j) 表示路径P的Qo S尺度:
若d(P) d(i, j) d( j,k) .......d(l,m) ,则称d为可加性参数;
若d(P) =d(i, j)×d( j,k)×.......×d(l,m) ,则称d为可乘性参数;
若d(P) =d(i, j)×d( j,k)×.......×d(l,m) ,则称d为凹性参数;
由以上分类定义可知,时延、成本等属于可加性参数,分组丢失率等属于可乘性参数,带宽、节点剩余能量等属于凹性参数。有关文献中已经证明,如果当路由选择过程中需要考虑的约束条件包括两个或两个以上的可加性参数或者是可加性参数和可乘性参数的组合时,此时的Qo S路由选择就是一个NP完全问题,如要寻找最小成本的最短路径和最小时延的最小成本路径,都是NP完全问题。这种情况下通常利用启发式算法寻找次优解。
基于以上难点,要在拓扑变化很快的网络中实施Qo S路由几乎是不可能的。但由于一般情况下,网络拓扑的改变不会非常频繁,且业务应用有一定的自适应性,因此在这种情况下实施Qo S路由是合理且可取的。
2实施QoS路由的优点
目前大部分的路由协议均用最短跳数当衡量路径好坏的标准,对于普通数据业务这种方法可行,但对于多媒体业务及实时业务而言这种方法则不太适用。为对业务提供Qo S保证,必须对流入网络中的数据量进行控制,实施Qo S路由就是实现接纳控制的关键。
实施Qo S路由的主要优点有:
(1)使得网络能够支持已有的和新出现的多媒体服务及应用的要求,例如IP语音等对网络有特定Qo S要求的新应用;
(2)使得网络可以对流入的业务进行接纳控制,即在路由选择过程中同时计算了该路径所能提供的Qo S能力,网络控制机制根据该路径的Qo S能力来决定是否接受新的连接;
(3)对网络中的服务保证和通信进行区分,这也是在单个网络中同时进行语音、视频、数据业务传输所必需的服务要求;
(4)通过使用Qo S路由可将业务量分配到不同的路径上, 不仅可以实现负载均衡,也能满足多种业务对Qo S的要求;
(5)使得网络提供商除了提供现有的尽力而为的服务种类以外,还可提供奖赏服务;
(6)在各种新型网络服务中有很重要的作用,例如虚拟专用网络。如何提高网络对Qo S的保障能力是Qo S研究的重点工作,而保证用户对Qo S的需求则是研究的最终目的;
(7)资源预留协议使得寻路过程朝着资源充足的路径行进,提高整个网络的资源使用效率。
3QoS路由协议
3.1度量参数的选择
衡量Qo S的指标有很多种,如时延、带宽、吞吐量、分组丢失率等等,由于寻找一条满足多个Qo S要求的路径通常是NP完全问题,特别是在移动自组网中,拓扑结构的动态变化性, 要求网络尽可能少地交换控制信息,所以一般来说不采用实现多维Qo S要求的方法,而应根据具体实际情况选择一两个较关注的合适的指标。由于所选择的Qo S度量参数反映了业务应用所关心的网络特性并定义了提供Qo S保障的类型,因此合理选择Qo S度量参数非常重要。
通常选择分组丢失率或链路可用带宽作为Qo S度量参数, 因为这两个参数最能反映出无线信道的质量和链路状态的变化,并且这两个指标也较容易获取到。如带宽指标,可通过节点间的信息交互来得到邻居节点的可用带宽,从而作出后续是否转发的决策;而时延指标,由于获取时延本身就存在时延的问题,因而不能及时反映网络拓扑的变化;网络吞吐量指标的计算则较为复杂,也不适合作为Qo S参数。
需要注意的是,一个节点的最大未用带宽并不等同与最大可用带宽,某节点的可用带宽不仅与本节点产生的流量及通过本节点转发的流量有关,还与和本节点共享信道的邻居节点的业务量有关,因为邻居节点进行业务传输时也会对本节点产生干扰。假设节点i的最大带宽是Ci,用lij表示节点i到节点j的业务流量,包括节点i产生的及转发的流量,用MUBi表示节点i的最大未用带宽,用MABi表示节点i的最大可用带宽,则
其中, Ni、 Nj分别表示节点i和节点j的邻居节点集合。
最大未用带宽就是节点总带宽减去本节点上所有业务使用的带宽,是通过节点本身计算得到的,是一个本地的概念,而最大可用带宽则是在最大未用带宽基础上,减去本节点所有邻居节点业务使用的带宽,节点需要知道周围邻居的带宽使用情况才能计算得到。
吞吐量就是单位时间内目的端收到的比特数。要计算出吞吐量,节点需要知道网络的整体状态。而在拓扑动态变化的移动自组网中,节点获取其邻居节点的信息都不容易,获取网络整体的状态信息就更难。并且若业务流量波动较大,计算吞吐量时选择的时间范围不同,得到的计算结果差异也会较大。因此,一般不适用吞吐量作为Qo S参数。
3.2度量参数的组合方式
根据网络的具体实际情况,选择出合适的Qo S度量参数, 对于存在多个度量参数的情况下,在路由选择算法中使用时其组合方式可以是单混合度量参数,也可以是多度量参数。
3.2.1单混合度量参数
通过自定义计算方法将多个度量参数归一化成一个参数, 例如若算法中考虑的Qo S度量参数有带宽、时延、包丢失率, 分别用B(P) 、 D(P)、 L(P) 表示,用F(P) 来表示路径的带宽、 时延、包丢失率函数, F(P) =B(P) ÷[D(P)×L(P)] ,在路由选择过程中选择具有最大F(P) 的路径。
但由于各度量参数的计算方法不同, F(P) 的计算准则较难确定,很难得到最优的Qo S路由算法,使各Qo S度量参数均最佳,因此,该方式一般只作为辅助参考。
3.2.2多度量参数
在路由选择算法中对每个度量参数都进行考虑,使每个参数都满足Qo S要求。主要方法有多优先级判断、界定参数。
(1)多优先级判断
根据业务具体需求对各个度量参数的关注程度对度量参数进行优先级的排序,在多条参数均满足Qo S要求的路径中,对比优先级最高的度量参数,选择具有最大该度量参数的路径; 若还存在多条路径时,则对比优先级次高的度量参数,直到选出最终使用的那条路径。
例如,若某业务对带宽、时延、包丢失率有要求,若有多条该三个参数均满足最低要求的路径,那么依靠自定义的优先级进行路由选择。如,对三个度量参数的关注程度由高到低依次是带宽、时延、包丢失率,那么业务先在可选路径中选择带宽最大的那条路径,若存在多条带宽最大的路径,则再在其中选择时延最小的那条路径,若还存在多条时延最小的路径,则再选择包丢失率最小的路径。
(2)界定参数
通过某种函数的映射,将连续的参数转换为整型的参数, 可以降低算法的复杂度和路由信息的开销,但最后选择的路径有可能不是最优的。
3.3QoS路由算法的选择
根据具体应用需求选定了Qo S度量参数和组合方式,就可以根据所获取的网络状态信息,进行有Qo S保障的路由选择。 目前路由选择所采用的方法大多是基于Dijkstra算法或Bellman-Ford算法的改进,该过程可以由源节点独立完成,即源路由,也可以由多个节点协作完成,及分布式路由。
3.3.1源路由
在源路由中,网络中的每个节点均保留全网的网络状态信息,并周期性更新,因此全网的系统开销非常大,并且还可能存在不准确的路由信息,易导致错误的路由选择的结果。
为减少节点存储的状态信息,将网络进行分层,设置分层路由,但这样组内的节点无法即时得到实时且正确的组外节点的状态信息,虽然系统开销小了,但是更增加了状态信息的不准确性,更易导致错误的路由选择的结果。
3.3.2分布式路由
在分布式路由中,网络中的每个节点都维护一张到达目的节点的下一跳节点的路由表。当节点接收到数据包后,通过查找自己存储的路由表就能知道该朝哪个节点继续转发。节点维护信息的成本相对较低,路由信息也比较准确,相对于源路由来说复杂性略高。
3.4QoS路由的维护
与普通路由维护不同的地方就是,Qo S路由的维护不仅只是维护路由的通断,还要看链路状态改变后是否仍然满足Qo S要求。
对路由信息的维护应该在路由更新的频率及消息的大小两方面均能够自适应地调整,以在系统开销和路由准确性上进行合理的折衷。
目前有一种可行的办法是设置一个变化门限值,当节点的状态信息超过该门限值时就进行信息交互,同时尽量维持现有路由而不进行改变,从而减少系统的开销和性能的抖动。若为每个业务流均维护路由信息,易导致路由表过于庞大,可以将网络进行分层,节点只需要考虑与组相关的状态信息,缺点是这些状态信息较片面,只能部分真实地反映全网信息,从而影响路由信息的准确性。
另一种方法则是采用按需的Qo S路由算法,在有业务请求时才进行Qo S路由寻找,缺点就是找到路由的时延较大。
由于移动自组网的动态变化特性,只能提供软Qo S保证, 即在链路连接未断时可以保证Qo S,但链路中断或者失效后, 就需要依靠路由重寻、备份路由、路由修复、自适应等方法来减小Qo S路由中断产生的影响,尽可能平缓地实现对服务质量的过渡。
4研究现状
由于Qo S路由协议在移动自组网中越来越多的应用,近年来已有不少研究者提出了一些有价值的移动自组网的Qo S路由协议。对于其设计思路主要分为两种:一种是在传统路由协议基础上进行改进,另一种是根据移动自组网的特点及Qo S约束条件,设计新的带Qo S保证的路由协议。
4.1对传统协议进行改进
为保证Qo S的需求,对传统的路由协议进行改造。在节点处增加对Qo S信息的维护,可以在路由表以及协议控制信息中增加相应的Qo S字段,如带宽和时延等等,在计算最短路径的同时也对各种Qo S信息进行更新,各个节点依据Qo S信息来决定是否对控制消息继续进行转发,或者是否建立新的通信连接。
在现有的协议中,很多协议例如按需距离矢量路由(Ad hoc On-Demand Distance Vector Routing,AODV)协议、动态源路由(Dynamic Source Routing,DSR)协议等都是按需路由协议, 利用这类路由协议按需的特点,且若采用最小带宽作为Qo S保证指标,就能大大降低Qo S路由的复杂度。在路由查找过程中, 控制消息中加入带宽字段,中间节点收到该消息后,先判断本节点处的带宽资源是否能满足Qo S要求,来决定是否继续转发, 依此准则,最后目的节点收到该消息后,就能找到一条满足所需带宽要求的路径。
在传统路由协议基础上进行改进的典型的Qo S路由协议有基于Qo S的AODV路由(Qo S support Ad Hoc on Demand Distance Vector Routing,Q-AODV)协议、提供Qo S支持的最优化链路状态路由协议(Qo S based Optimized Link State Routing Protocol,Q-OLSR)等。
Q-AODV协议是在经典的移动自组网按需路由协议AODV协议上改进而来的,其实现的基本工作原理就是在AODV协议的路由表和控制消息中增加内容,附加上Qo S相关信息,增加的内容有可忍受最大时延、可用最小带宽、时延请求保障节点列表和带宽请求保障节点列表。其工作流程与AODV协议类似,只是在各个过程中都考虑上Qo S因素。各节点与其邻居节点共同确定可用时隙,通过从源节点到目的节点传播过程中不断更新Qo S信息计算出各条路径的总时延和可用带宽,若所得路径能够满足业务要求就使用RREP消息建立链路。
Q-OLSR协议是在经典的移动自组网主动路由协议OLSR协议基础上改进而来的,其核心概念是多点中继(Multiple Point Relay,MPR)。在OLSR协议中加入Qo S保证时,会受到一些限制,例如,OLSR协议以覆盖的两跳邻居节点最多作为MRP节点的选择依据,由于未考虑链路带宽,有可能忽略某些带宽较大的链路,并且在OLSR协议中,非MRP节点只与自己的邻居节点通信,不进行中继转发,链路大部分时间处于空闲状态。Q-OLSR协议针对这些限制因素,对MRP节点的选择方法进行改进以满足Qo S要求。
4.2设计新的路由协议
根据移动自组网的特点及Qo S约束条件,从而提出一些新的带Qo S保证的路由协议,典型的协议有核心提取分布式Qo S路由(Core Extraction Distribution Ad Hoc Routing,CEDAR) 协议、带Qo S约束的组播路由协议(Qo S-based Multicast Routing Protocol,QMRP)、分级式Qo S组播路由协议(Hierachical Qo S Multicast Routing Protocol for Mobile Ad hoc networks,HQMRP) 等。
CEDAR协议的基本思想是在全网节点中选择部分节点作为核心集合,由这些核心节点在有业务需要时计算Qo S路由, 链路状态信息的交互也只需要在这些核心节点间进行,减少了信息交互的开销。
QMRP协议的Qo S保证综合考虑了带宽、时延、节点移动速度和节点剩余能量等因素,给每个因素设置一个相应的门限, 只要其中某一项超出了门限值,就认为这条路径不满足Qo S要求,不能算成有效路径。在该协议中,组播树的形成过程是各节点及相应链路在满足达到门限值要求的前提下渐近生成的。
HQMRP协议是一种基于簇结构的Qo S组播路由协议,每个节点只需要维护本簇内的组播路由信息和其他簇的概要信息,不需要维护全网的状态信息。网络中所有节点都支持多种Qo S约束,簇内的每个节点均周期性地检测其输出链路上的时延,并通过与簇内其他节点交互该链路延迟信息来维护簇内节点的路由表及进行网关节点的路由更新。
4.3基于移动自组网的QoS路由协议对比
根据对以上几种路由协议的分析可知,一个理想的移动自组网的Qo S路由协议,应充分考虑到网络的自组织性、网络拓扑结构变化的适应、单向链路的支持、有限的传输带宽、生存时间、在组播中的应用需求、移动设备主机能量及内存大小的局限性等等因素,中对前文中介绍的移动自组网Qo S路由协议进行了对比。
(1)主动/按需方式:在移动自组网中,根据节点获取网络状态信息的方式,可以将Qo S路由协议分为主动路由协议和按需路由协议。主动路由协议周期性交互并更新信息,尽力维护全网中的路由信息,并且当拓扑结构发生变化时,向全网中传播路由更新信息以维护整个网络信息的一致,按需路由协议则只在源节点有需要时,才创建并维护路由;
(2)分布式操作:移动自组网在自然灾害的救助、军事通讯等方面均有广泛的应用,应用场景要求其应具备较高的鲁棒性,而集中式路由协议很难满足这种要求,所以自组网协议均采用分布式操作方式;
(3)单向链路的支持:移动自组网是基于无线环境中的网络,节点能量、发射功率、所处地理环境等均会对网络性能产生影响,而在无线环境中单向链路出现的可能性较大,这也给路由协议的实现带来了新的困难;
(4)Qo S参数的选择:在移动自组网中采用Qo S路由, 需要根据具体情况选择不同的Qo S参数。在移动自组网中Qo S参数既可以包括节点本身的参数,如节点能量、内存大小、处理能力等,也可以包括链路参数,如链路带宽、时延等。必须根据具体的业务及网络状态来选择Qo S参数,想同时满足多个Qo S要求是难于实现且不切合实际的;
(5)组播功能的支持:在资源稀缺的移动自组网中,组播支持具有非常重要的意义。在组播通信中可以更高效的利用网络带宽并减少节点能量的耗费,因此在移动自组网的Qo S路由协议中支持组播功能,也是自组网网络协议的一个重要研究方向。
5结语
路由协议是网络中最基本的重要功能之一,Qo S路由协议则是针对未来网络发展的需要而加入的功能,根据业务通信的需求提供满足条件的路由,并且能够更有效地利用网络资源。 但目前移动自组网中较典型的Qo S路由协议均是采用传统的分层设计架构,由各层独立完成各自的工作,其他层的一些有用信息路由层则无法使用。跨层设计架构将各层的设计因素结合在一起,使各层间能交互有用信息,路由层可依据其他层提供的有用信息进行路由过程,可有效地提高网络资源的利用率, 更好地适应拓扑的动态性。因此在未来的工作中,可以把跨层设计作为移动自组网中Qo S路由协议研究的一个重要方向。
在移动自组网中节点能量也是一个非常重要的因素,在很多情况下会影响到网络的整体性能,通过节能设计可以延长节点和整个网络的寿命,因此如何更好地节约主机能源,设计基于能量的Qo S路由,也是移动自组网中路由协议研究的一个重要方向。
组网协议 篇5
随着经济的发展, 交通业也在飞速发展, 道路车辆数目激增, 道路交通安全形势日趋严峻。作为智能交通系统[1]重要基础之一的车载自组网[2]正是在此需求背景下提出。
车载自组网是移动自组网[3]的一种特殊形式, 由于网络节点频繁移动的特性, 路由技术始终是其研究的重点。目前按照路由发现策略的不同, 路由协议可以分为两种:被动式路由协议 (OLSR等) [4]和主动式路由协议 (AODV和DSR等) [5,6]。其中DSR路由协议在路由控制开销、对网络拓扑的适应能力、节省能耗等方面更具有优势[7]。但由于网络节点的频繁移动会导致拓扑结构的频繁变化, DSR缓存路由表更新不及时, 路由发现时引入许多不必要的节点, 造成路由绕路和断开, 从而路由发现和维护过程频繁发生, 最终导致数据传输的时延增加和丢包率增加。
针对以上DSR存在的问题, 本文提出一种带有分组的路由协议 (GDSR) 。它是对DSR路由协议的一种改进, 这种路由协议在组内使用组内路由协议, 在组间使用DSR路由协议。组内的组头保存组内所有节点的信息[8,9], 在组内节省了路由发现的过程, 这样相比DSR路由算法可以减少丢包率和数据传输的延时, 使得这种算法更好的适应车载自组网拓扑结构的频繁变化。
1 GDSR路由协议
1.1 分组的必要性
当车辆进行通信时, 需要发现路由。在传统的DSR路由协议中, 车辆节点是洪泛的发送路由请求寻找目的节点, 这种洪泛的请求方式使得数据传输的时延较大。同时节点的移动性, 容易造成数据包丢失。如果对车辆进行分组, 并设定组头对组进行管理, 组头可以协调信息的传输, 节省组内的路由发现时间, 因而减少了数据传输的时延。组结构的相对稳定性, 可以减少数据传输的丢包率。分组必要性如图1所示, 假设在DSR路由算法中, B与G通信的路由是B-C-D-E-G。而对车辆进行分组后, B到G的路由可以通过组头节点B、F和公共节点D很快找到路由B-D-F-G。
1.2 组协议
在GDSR协议中节点分为四类:组头, 组成员, 网关, 孤立节点。组头是一个组的中心节点, 它负责管理这个组的通信, 管理组内成员以及维护组间路由。组成员负责维护组内的通信。网关是同时属于多个组的节点, 这里规定一个节点至多属于两个组。孤立节点是没有加入任何组的节点。
1.2.1 组的构建
当两个节点的运动方向相同、运动速度之差不超过1m/s时, 它们之间的相对移动比较缓慢。因此, 为了提高组内结构的稳定性, 组的构建以节点的运动状态为依据, 只有移动方向相同、速度在同一等级的节点, 才能成为一个组。初始化时, 每个节点都是孤立节点, 节点周期性的广播节点信息, 来获取周围节点的信息, 通过周围节点的信息寻找能构成组的节点。若不存在运动状态相同的节点, 这个孤立节点将成为新的组头, 并产生一个ID, 这个ID用于区分不同的组。
1.2.2 组的维护
为了维护组内结构的稳定性, 组头、组成员和网关需要周期性的广播节点信息, 让组内成员获知自己还存在。组头周期发送的信息包中包括组的ID和组内成员名单等信息。组头若在一定时间内没有收到组成员或者网关的信息包, 则认为该节点已经离开分组, 并把这个节点从组内成员名单中删除。
组成员和网关在接收到组头的信息包之后, 会设置一个计时器, 等待下一个信息包发送过来, 当超过计时器设置的时间, 下一个信息包还未发送过来, 则认为组头已经离开这个分组, 这时需要重新选择新的组头。在选择组头时, 如果在组内随机选择, 可能会选择在组边缘的车辆成为新的组头。而处于组边缘的车辆随时可能会离开分组, 导致组头的选择频繁发生, 这样选取头节点的效率会大大降低而且这个组在一段时间内会接收不到有效的信息, 这对汽车的行驶安全会构成一定的威胁。如图2所示, 车辆F是组边缘的车辆, G为离开的组头。
针对这个问题本文采用K-medoids聚类算法的思想来选取新的组头。K-medoids聚类算法分为五步:①从含有M个数据对象数据集中任意选取K个数据对象作为K-medoids聚类的中心。②分别计算数据集余下的数据对象到各个聚类中心的距离, 并将数据集余下的数据对象分配到离自己最近的聚类中。③所有的数据对象分配完成后, 顺序选取一个数据对象来代替原来的聚类中心, 并计算代替后消耗的方差E, 选择E最小的数据对象来代替所有的聚类中心点, 这样K个中心点就改变了。④与前一次的聚类中心相比较, 如果发生变化转到②, 如果不发生变化转到⑤。⑤输出聚类结果。
对于车辆的分组, 就相当于一次聚类的完成, 一个分组就是一个聚类。当组头消失, 就相当于要选取新的聚类中心。假定组头消失后, 先选图2中的A为头节点, 根据K-medoids聚类算法第③步, 顺序选择其余几个节点为聚类中心, 计算代替后消耗的方差E。E的计算方法如下:
其中, k代表组内每辆车节点, n代表组内车节点的数量, i代表除了选定为中心节点之外的车节点, (x, y) 为车辆在二维坐标下的坐标值, 代表了车辆在路上所处的位置。算出EA, EB, EC, ED, EE, EF之后比较大小, E值最小的节点成为新的组头。
当孤立节点需要加入某个组时, 首先广播信息查询分组, 查询其通信范围内是否有运动状态相近的组, 经过一段时间后, 如果收到一个或者多个组头的回复信息, 则选择最早收到的组头信息加入分组。否则, 该孤立节点成为新的分组。
节点的移动性还会导致两个运动状态相同的组头相互靠近, 造成资源竞争和信道冲突。此时, 成员数较少的组头将放弃组头的地位, 并向组内广播解散分组, 宣布组结构失效。
1.3 GDSR路由协议过程
路由协议过程分为组内路由协议和组间路由协议。
1.3.1 组内路由协议
在组内路由协议中, 为了避免信道竞争造成的通信阻塞, 提高数据传输的实时性, 组内的数据规定只在组成员间进行传输。
源节点首先检查组内成员列表, 确定目的节点所属的组。如果源节点和目的节点处于不同的组中, 则进入组间数据传输阶段, 源节点将数据分组发送到所属的组头, 组首再根据组间路由协议将数据传输到目的节点。如果源节点和目的节点处于相同的组内, 则源节点直接将数据传送到组头, 然后由组头将数据传送到目的节点。由于组头的位置位于组的中心位置, 所以组内的数据传输不会出现局部优化的问题。
1.3.2 组间路由协议
组间路由协议采用DSR路由协议, 其中包含路由发现过程和路由维护过程。
1.3.2. 1 路由发现
路由发现过程如图3所示。
其中, RREQ包的格式如表1所示。
其中, Sid为源节点的ID号, Did是目的节点的ID号。Route record是源节点到目的节点所要经过的节点序列的ID, 这个关于节点序列号的记录在一开始的时候只包含源节点的ID号。Request id是源节点决定的唯一的路由请求序列号。
RREP包的格式如表2所示。
其中, Did是目的节点的ID, Data route是源节点将要发送的数据分组所要经过的路由, Reply route是RREP包所要经过的路由。
1.3.2. 2 路由维护
当路由发现过程完成后, 根据发现的路由, 数据分组会沿着源路由中的节点列表依次转发, 转发该数据分组的每个中间节点都要负责证实数据能否通过本节点到达该条路由中规定的下一跳节点。转发数据分组的每个中间节点都要负责该条源路由的维护工作, 例如路由是A-B-C-D, 节点B责证实数据分组是否通过B达了C, B会向C发送一个应答请求包, 来明确要求该条源路由的下一跳节点C直接回送一个DSR软件应答, 节点B在收到应答后, 可以要求节点C在一段短暂的时间周期内不再做出回答。为了防止分组丢失造成没有得到应答, B会设置一个最大允许重发次数, 如果超过这个次数仍然未收到应答, 则认为链路断开。如果发现链路断开, 则链路的上游节点会从其路由缓冲期中删除包含这条中断链路的所有路由, 并向源节点发送一个路由错误包RERR, 包的格式如表3所示。
其中, Node1表示断开链路的上游节点ID, Node2表示断开的链路的下游节点的ID, Did是目的节点的ID, 而Rerr route是RERR包到达源节点所需要的路由。沿途转发RERR包的节点会从其路由表中删除包含该条断开链路的所有路由。源节点收到RERR包之后, 会将失效的路由删除, 查看路由表中是否存在另一条到达目的节点的路由, 若有立即使用新的路由发送数据分组, 否则重新发起路由发现过程。
2 实验仿真结果和分析
2.1 实验环境
在NS-2.34平台上对DSR和GDSR协议进行仿真实验。节点随机分布在1000m×500m区域中, MAC层协议为IEEE802.11, 节点的传输范围为250m, 数据分组的类型为CBR, 大小为512b, 分组发送速率1分组/s, 仿真时间为500s。
2.2 实验结果及分析
影响路由协议性能的因素很多, 本文主要分析节点的移动速度和节点的数量对端到端的平均延时和丢包率的影响。
2.2.1 节点数量对协议性能的影响
节点的平均速度本文随机设定为10m/s~20m/s之间, 节点数量分别设为30, 40, 50, 60, 70进行仿真。
当节点较少时, 链路会经常断裂, 频繁的路由维护过程会导致传输延时的增加。当节点数量较多时, 路由控制信息的增加也导致了平均延时的增加。因为GDSR协议中加入了分组, 在组内数据的传送较为直接, 减少了路由获取的时间, 所以GDSR相比DSR而言, 端到端的时延较小。图4给出了平均时延随节点数量增加的变化情况。
随着节点数量的增加, 路由控制信息也会增加, 很多数据分组会因为超时被丢弃, 导致丢包率增加。在GDSR协议中, 因为组内的丢包率较小, 所以整体的丢包率比DSR协议小。图5给出了丢包率随着节点数量增加的变化情况。
2.2.2 节点速度对协议性能的影响
节点数量本文选为50, 平均速度分别设为10、20、30、40和50m/s进行仿真。
随着节点平均速度的增加, 网络拓扑结构变得不稳定, 所以端到端的延时都在增加。GDSR协议因为加入了分组, 组结构相对稳定。而且组内协议中因为有组头的管理, 在组内不需要查找路由, 只要发送给组头, 让组头根据成员列表进行转发即可, 所以端到端的时延比DSR协议要小。图6给出了平均延时随着节点平均速度增加的变化情况。
随着节点平均速度的增加, 传输路径会频繁的断开, 所以两种协议的丢包率都会增加。GDSR协议中的组建立是在运动状态相近的情况下建立, 当平均速度增加, 不太会影响组内的丢包率, 但是会影响组间通信的丢包率, 所以相比DSR路由协议, GD-SR路由协议的丢包率较低。图7给出了丢包率随着节点平均速度增加的变化情况。
3 结束语
本文分析了DSR路由协议存在的问题, 在DSR协议的基础上提出了带有分组的GDSR协议。GDSR路由协议以节点的运动特性进行分组, 并结合DSR路由协议进行路由决策。实验表明, GDSR路由协议相比DSR路由协议能降低端到端的时延和丢包率, 更好地适应车载自组网多变的拓扑结构。在日后的研究中, 将会对组间的路由协议进行改进, 使得路由协议能达到更好的数据传输效率。
参考文献
[1]Internet ITS consortium[EB/OL].http://www.internetits.org.2006.
[2]Toor Y, Muhlethaler P, Laouiti A.Vehicle ad hoc networks:applications and related technical issues[J].IEEE Communications Surveys and Tutorials, 2008, 3 (10) :74-88.
[3]郑少仁.Ad Hoc网络技术[M].北京:人民邮电出社, 2005.
[4]Clausen T, Jacquet P.Optimized Link State Routing Protocol (OLSR) [S].IETF RFC 3626, 2003.
[5]Perkins C, Belding-Royer E, Das S.Ad hoc On-DemandDistance Vector (AODV) Routing[S].IETF RFC 3561, 2003.
[6]Johnson D, Maltz, D, Hu Y.The Dynamic Source RoutingProtocol for Mobile Ad hoc Networks (DSR) [S].IETF Internet Draft, draftietf-manet-dsr-10.txt, 2004.
[7]孟利民, 宋文波.移动自组网路由协议研究[M].北京:人民邮电出版社, 2012.
[8]Chen Wai, Cai Shengwei.Ad Hoc Peer-to-Peer Network Architecture for Vehicle Safety Communication[J].IEEE Communication Magazine, 2005, 4 (43) :100-107.
组网协议 篇6
某型手持式信息支持设备上配备[1]的无线数传模块具有如下特性:工作于超短波频段、窄带、存储16个频分半双工物理信道、工作时由编程指定单一物理信道进行模块与模块间的点对点通信, 并由嵌入式系统控制其信道预置和收发转换。保障任务的网络化与一体化变革对该设备提出了新的组网需求, 现在面临的问题是如何在既定的物理层基础上开发一种稳定且相对可靠的组网协议以实现点对点和点对多点通信, 难点在于MAC层采用何种接入机制控制移动终端对共享无线信道进行相对公平的访问。
无线移动领域中典型的接入机制有:有冲突的随机接入机制 (CSMA等) 、无冲突的固定分配接入机制 (TDMA, FDMA, CDMA等) 、轮询机制 (令牌环) 。但这些典型的接入机制都不能很好地适用该组网需求[2]。首先单模块单信道的硬件环境无法采用固定分配机制实现组网, 也无法为DBTMA协议 (双忙音多址接入协议) 提供独立的控制信道和数据信道[3]。其次, 由于系统工作在通信频次不确定且峰值持续时间较低的突发式通信模式中, 采用中心节点控制下的周期性轮询与各移动节点分时应答相结合的802.11协议中的PCF (Point Coordination Function) 接入方式虽提供了适用于点对多点的集中控制下的网络接入。但在非数据通信周期内产生的大量空应答帧[4], 伴随着由此引发的发射所付出的功率损耗与信号解析所付出的嵌入式系统计算资源占用, 使PCF在突发式通信应用中整体效率低下。而采用RTS/CTS信道预约机制的CSMA/CA协议, 利用所有入网终端均能收到的CTS帧中的时间信息对数据发送期提供保护, 使其不受其它终端发起的RTS干扰[5]。但其致命弱点是无法消除迟入网终端 (在其它终端的CTS发出之后才开机入网) 的RTS所带来的干扰, 也不适用于突发式环境。
1基于信道切换的冲突避免协议
为解决突发式通信环境下的单信道组网, 本文利用数传模块存储16个信道, 并可在嵌入式系统控制下进行工作信道实时跳变的特点, 对DBTMA协议进行改进使其能工作于单信道半双工系统。尽可能地简化控制流程和信令结构以适应低速网络的传输要求, 提够系统信息传输效率。用RTS/CTS握手与信道跳变相结合的方式, 提出基于信道切换的冲突避免协议CSMA/CD-SC (CSMA/CD based on Swift-Channal) , 用较少的开销实现了控制信道上的自由竞争与数据信道上的独占式保护。典型应用中全网由包含10个信息支持设备移动终端的分组与作为一级中心节点的计算机端构成。可实现同分组内移动终端间点对点通信与各分组内移动终端与中心端的点对多点通信。所有设备均使用一部相同的数传模块作为射频接入手段, 在现有硬件不变的条件下实现了快速组网。
1.1协议描述
协议使用三种控制帧和一种数据帧运行于两个双向逻辑信道, 分别为控制信道和数据信道, 其中控制信道为常驻信道。每个分组的逻辑信道由16个物理信道中的任意两个进行承载。四种帧的详细情况如表1所示, 其中预先约定的ID号做为各终端的唯一识别标志。
1.2基本工作流程
如图1所示, 收发双端常驻于信令信道, 当终端欲与中心通信时, 先发出RTS信号, 然后等待。中心接收到RTS时, 发出CTS, 同时跳转到数据信道准备接收数据。终端接收CTS后, 跳转到数据信道, 并发送数据。发送完毕后, 自动跳转回信令信道。中心接收完数据后 (以接收数据帧的组结束标志为判断依据) 也返回常驻信道。超时等待在死锁解除部分论述。
1.3相关问题说明
1.3.1 碰撞避免
由于采用信道切换, 不用在RTS/CTS帧中记录数据传输的保护时间长度, 与CSMA/CA相比简化了RTS与CTS的结构。使在自由竞争时间内的RTS碰撞概率得到进一步下降。又由于中心发出的CTS能被网内所有终端收到, 如帧解析后得知授权方不是本机则对本机的发送请求进行延迟。当数据通信开始时由于信道的跳转, 其它终端发起的RTS被屏蔽, 直到一次数据通信结束才解除, 保证了数据的正确接收。
1.3.2 DEADLOCK解除机制
等待发送的死锁:以下两种情况会造成终端等待发送的死锁:当中心已处于数据通信模式, 其他终端再次发起RTS后得不到CTS时;由于突发性的干扰使RTS、CTS未被正确接收时。通过如下方法解除:在RTS发送的同时, 超时等待事件开始计时, 当计时完毕时仍未收到CTS则停止等待, 并向用户发出发送失败的通知, 由用户再次提起通信申请。
等待接收的死锁:当中心发出CTS信号后跳转至数据信道等待接收, 由于突发性干扰使接收数据的组结束标志丢失或误码, 则中心无法返回常驻信令信道, 整个系统陷入死锁。因此在中心设置超时等待事件, 在跳转至数据信道时开始计时, 当计时完毕前收到数据帧的组结束标志则正常跳转回常驻信道, 当计数超时还未收到组结束标志则强制跳转回信令信道, 并发送NAK至终端, 并经由应用层告知用户上次通信出错, 需要再次传输。
1.3.3 功耗控制
为了增加具有便携性的移动终端的续航力, 必须对能量消耗集中的射频模块部分进行严格的功率控制, 对其直接控制的MAC层协议发挥着重要作用[6]。在此采用以下三种手段降低功耗。首先是减少数据流量, 对通信中所用到的固定信息用代码表示。应用层采用选择式表单, 在数据提交到MAC层之前由同时存储于收发双端的编码数据库进行压缩编码, 可以实现将大部份的通信流量控制在一个63字节的数据帧之下。其次是减少信令开销, 一次典型的成功通信需要大约67字节的空中流量, 其中信令占4字节, 开销在6%左右, 且随着数据包的增多该比例会继续下降, 少于其它同类型组网协议的开销。最后, 由于采用两种逻辑信道, 当终端常驻于信令信道时, 射频模块处于低功耗工作模式。且在发送RTS之前如侦听到他方终端发送的RTS信号, 将自动经过一次通信所需要的典型时间延迟后才发送本机的RTS, 减少由于不必要的碰撞重发导致的功率损耗。
2仿真与应用实验
2.1性能仿真模型
由于中心端一次只和一个移动终端通信, 且其它终端未获得CTS则退出本次通信, 所以本协议可用单通道损失制 (M/M/1/0) 的排队模型描述。M/M/1/0系统的效率指标如下:
相对接通概率为
λ为单位时间内的平均呼叫数,
L=T1+2Ts+T2 (2)
T1为中心收到RTS到发出CTS的时间, Ts为信道转换所需要的时间, T2为接收数据帧所需要的时间。经过软硬件调试, 测得T1=200 ms, T2=300 ms, Ts=500 ms, 于是有
为描述信源的突发特性, 用ON/ OFF模型作为数据源模型[7], 它描述了由一系列交替的突发期与静默期所组成的业务特征, 突发期和静默期严格交替, 持续时间分布相互独立, 且具有 “重尾” 特性 (方差无穷大) 。由于在本协议中, 每个移动终端每次只发出一个固定长度的RTS帧, 所以突发期持续时间固定, 突发性主要由静默期持续时间的变化表现。静默期持续时间服从Weibull分布。
Weibull的分布函数为
F (x) =1-e- (x/β) α (3)
其数学期望为
E (x) =βΓ (1/α+1) (4)
式 (4) 中
分析图2可知, 在突发强度较高的情况下, 系统性能随容量的增加, 下降较慢;当突发强度减弱, 直至完全退化为指数分布时, 系统性能随容量增加而急剧下降。
2.2应用实验
利用10台信息支持设备与一台做为中心的计算机进行组网通信实验。10台终端随机分布在100 m到1 km的校园环境中, 不采用扩容方案。进行三组实验, 第一组各终端在规定时刻同时发送, 重复30次。第二组各终端错开1 min进行发送, 同样重复30次。第三组无时间规定, 各终端时间随机发送30次, 在30 min内完成。发送内容为相同的单份表单数据。结果如表2所示。
结果表明由于信令信道采用抢占式机制, 当各终端同时提交RTS时容易发生碰撞导致通信失败, 同时由于信令间的干扰导致死锁次数较多。当各终端发送时间有一定错位时, 有较高的发送成功率, 且几乎无死锁现象。模仿真实应用模式的第三组实验也有超过80%的成功率, 且无连续发送失败的记录。实验结果与仿真结果吻合, 证明本协议能在强突发环境中实现小分组间的组网通信需求, 且死锁解除机制能发挥预期作用。
3扩容方案
由先前的仿真及实验可知受硬件条件的约束CSMA/CD-SC协议采用的竞争与抢占模式适用于呼叫频次较低的突发性通信, 当大量的通信需求在短时间内发出则会在控制信道上产生大量RTS碰撞, 使RTS/CTS握手的成功率急剧下降。为了满足高用户容量或高吞吐量的需求, 可以在适当改变硬件条件的基础上对协议进行扩充。以下介绍两种扩充容量的方案。
方案一:适用于中心需要与多个分组进行通信的情况。中心节点在硬件上增加一部永驻于公共信令信道的通信模块, 在程序上引入消息队列机制。并增加一个不同分组共同享有的公共信令信道承载分组选择信令, 扩容后全系统可携带7个不同分组。各分组常驻于分组内信令信道, 当需要与中心通信时跳转至公共信令信道, 并向中心的模块1发送RTS, 中心将RTS存入队列, 如此时中心处空闲状态, 由消息处理机制将模块2调整至请求分组工作的信令信道, 并发出CTS, 随后步骤与基本协议相同。
方案二:适用于同一分组内同时间内有复数个通信需求的情况。中心节点由三部模块构成, 模块1常驻于信令信道, 模块2、3常驻于数据信道, 并引入队列机制。除信令信道由固定物理信道承载外, 两个数据信道均可在剩余的15个物理信道上跳变。RTS帧增加1位用于指示数据通信所使用的物理信道。同样在程序上引入消息队列机制。此方案虽增加了成本但提高了吞吐量与通信成功率 (RTS被抛弃的概率大为降低) , 且由于采用了灵活的信道跳变, 在一定程度上增加了抗干扰能力。
4结束语
由工作于嵌入式环境的通信模块特殊性能及要求出发设计的基于双信道的抢占式非同步冲突避免协议提供了一种在低速条件下的组网方法, 经过实验验证, 可在突发性较高的应用中稳定运行, 为进一步在此硬件条件下开发无中心的AdHoc等协议奠定了基础, 具有较大的现实意义。
摘要：针对应用于嵌入式系统的低速无线网络开发出一种工作于MAC层的基于信道切换的冲突避免协议 (CSMA/CD-SC) 。为基于嵌入式系统的某型手持式信息支持设备提供了点对点与点对多点的无线链路协议。围绕嵌入式系统与低速网络提供的单一信道半双工通信这一特殊环境, 在碰撞避免、死锁解除、功率控制等方面做了针对性设计, 并提出了相应的扩容方案。经仿真及实验表明, 该协议能够用较少的开销满足高突发性网络通信的需求。
关键词：低速组网,嵌入式环境,冲突避免,信道切换
参考文献
[1]梁伟, 全厚德, 张弛.基于PXA255的信息支持设备设计与实现.军械工程学院学报, 2006; (6) :014—016
[2]彭艺.军用分组无线网中的关键技术研究.成都:电子科技大学, 2005
[3]李便莉, 孙献璞, 邓梁.基于双忙音的多址接入协议的研究.现代电子技术, 2005; (18) :071—074
[4] William C Y Lee.Wirless&cellular telecommunications.Third Edi-tion.北京:清华大学出版社, 2008
[5]王彦波, 察豪.CC1020的点对多点无线组网研究.新器件新技术, 2009; (2) :039—043
[6]程跃斌, 林村河, 龚红伟, 等.基于无线网络的师旅救护所信息系统的研制与应用.医疗卫生装备, 2009;30 (5) :020—022
[7]王学东, 李建东.基于自适应扩频技术的多址接入协议.吉林大学学报 (信息科学版) , 2009;27 (5) :481—486
组网协议 篇7
低压配电网由于其具有分布广、用户数量多等特点,使其在节约资源、方便用户、减少安装费、实现多媒体通信等方面被广泛关注。但由于低压配电网电气负载环境的复杂性和介质环境的共享性、开放性和多样性的影响,造成通信可靠性低,使目前电力线载波通信的广泛应用受到限制和普遍质疑。针对建立网络中继提高电力线通信可靠性的方法,国内外的研究人员进行了一定的研究。其中,文献[1-2]提出基于蚁群算法的电力线载波通信组网方法在一定程度上解决了电力线载波通信网络的通信可靠性问题。笔者对蜘蛛织网的行为、圆形蛛网的结构特性、猎物在蛛网上信息传递机理等方面进行大量的研究[3],同时借鉴前人的相关研究成果[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],提出了基于人工蛛网通信模型,并将低压配电网的主要负责通信协议部分(Media Access Control,MAC)层网络转化成由多个人工蛛网组成的逻辑拓扑,制定了一种新的自动路由协议,建立了人工蛛网仿真模型,验证了该种新型网络结构及路由协议的优越性,试图为研究适合电力线载波通信网络的路由模式,提高电力线通信的可靠性,提供一条新的思路。
1 新型网络模型
1.1 人工蛛网拓扑
蜘蛛经过了约18亿年的进化,现在的蜘蛛网不仅具有优雅、超轻的结构,而且具有超级弹性和抗张强度,可以抵抗各种大风、昆虫等的冲击。即使有几个网格单元遭到破坏,它仍能作为网来捕获猎物,具有极强的抗毁能力。针对蜘蛛网的结构特点、蜘蛛的捕食机理以及人工蜘蛛网通信拓扑的构建等方面问题,文献[3]中已进行了详尽的阐述,并建立了双层六边形人工蛛网逻辑拓扑模型。本文以单层六边形人工蛛网为通信子网模型进行组网,并进行了相应的分析与仿真。
1.1.1 人工蛛网逻辑拓扑模型
电力线载波通信的时变性、频率选择性和强干扰性等特点,使电力线通信的组网方式具有其独特的特点,如,网络物理拓扑和逻辑拓扑具有时变性,没有专用的交换机和中继器,通信媒质共享信道,弱数据处理能力,一对多通信等。为保证一定的通信距离/组网规模,电力线通信组网通常需要通过路由器/中继器将同一个物理子网划分成多个逻辑子网。低压电力线通信网络是由星形网络和树形网络组成的混合网络。从物理层看,图1所示的单层人工蛛网除具有多个星形网络(如v1,v2,vh,v4,v5)和树形网络(如v1,vh,v3,v2,v4)外,还具有自己独特的环形网络(如v1,v2,v3,v4,,vm);从数据链路层角度,人工蛛网的结构是一对多、多对一的这种通信方式,与低压配电网的总线型逻辑拓扑相吻合,所以,不论从物理层还是数据链路层,人工蛛网结构都能作为低压配电网的组网结构。
1.1.2 人工蛛网数学模型
为了能更清楚地阐释人工蛛网的结构特征和建立新型路由模型,且为进一步研究蛛网提供理论基础,本文定义了人工蛛网的主要特征参数如下。
(1)Nr为围绕中心节点vh的蛛网层数,即同心圆层数。该参数反映人工蛛网的复杂度,同时也决定人工通信蛛网所覆盖的通信范围,本文中取值为1。
(2)Ns为中心节点vh与周边节点iv(i=,1,m)相连的蛛网轮辐数,即中心节点与相邻周边节点通信路径数量。
(3)Nn为人工蛛网总节点数,与Nr,Ns的关系如式(1)所示。
(4)Dw为蛛网直径,直接反映蛛网所覆盖的物理范围。
(5)Hm为网眼高度,是同一径向上相邻两层节点之间的距离。该参数反映网络的密度,与wD,Nr的关系如式(2)所示。
(6)Δθ为蛛网扇区角,即相邻两径向路径的夹角。
这样,蛛网中任一节点的位置可由式(4)所示的极坐标方程来表示。
其中:ri=i×Hm,i=0,1,,Nr,为径向方向上的路径长度;θk=k⋅Δθ,k=0,1,,Ns-1,为径向路径与水平线的夹角。这些只是网络的逻辑关系,因此式(2),式(3)可以标准化为式(5)、式(6)。
则式(4)可以简化为式(7)。
1.2 PLC网络的人工蛛网结构
在PLC系统中,下行方向定义为信息由基站传输到所有的用户终端,每个终端可以直接或通过中继间接收到下行信息;上行方向定义为用户终端传送信息给基站。上行方向的信息不仅可以被基站接收,也可以被其他用户终端接收。所以,从MAC层角度,PLC网络是一个树形物理拓扑下的总线型逻辑结构[19],如图2所示。其中BS(Base Station)为基站,负责网络内所有节点的数据采集及组网等。近、中、远的定义是根据收到BS广播信息的节点与BS的距离定义的,如BS一次广播后,收到该广播的节点定义为“近”,收不到该广播,且需要以“近”节点为中继与BS通信的节点定义为“中”、“远”节点是以“中”、“近”的节点为中继与BS通信的节点。基于网络的此种结构特点,本文建立这种基于蛛网结构的PLC组网模型。
低压配电网三相之间的衰减较大,在没有相间耦合器的情况下,低压配电网三相之间可以看作并列且相对独立的逻辑关系,因此可将其中某一相的逻辑拓扑作为重点研究对象。由于电力线通信数据传输距离有限,在实际应用中,某一相内可能只有离基站物理距离近的用户终端能与该相基站可靠通信。假设某相网络内用户节点总数为n,基站一次广播后有m(1≤m≤n)个节点能与之可靠通信,剩下n-m个用户节点虽然物理链路是连通的,但由于信号随传输距离的衰减等原因,不能与基站通信。为了解决这个问题,本文提出了基于单层蛛网的组网模型。
在m个能与基站可靠通信的节点中,假设相邻两节点间是可靠通信的,m个节点组成图1所示的m-1边蛛网结构,相邻节点之间能可靠通信,不相邻节点可通过节点h为中继进行通信。节点v1,v2,,vm代表用户终端节点。假定节点vh位于逻辑子网的中心(vh为v1~vm中的一个,1≤h≤m),其与所有周边节点均能可靠通信,功能与基站类似,负责收集其所在蛛网周边各节点的数据,维护子网内的路由以及与其他子网的中心节点通信。同时,由此节点发起对剩下的n-m个用户节点的组网广播。由于节点vh较基站与其余n-m个节点物理上的相近性,所以当vh继续发起组网广播后,有新的节点收到vh的组网广播,这些新的节点构成新的人工蛛网子网。然后,新的子网选取中心节点vm+1,确定子网节点数目,由vm+1与上一子网的中心节点vm+1保持数据通信,同时,进行新一次的组网广播,会有新的节点收到该广播。依次类推,最终该网络内的所有节点组成了多个类似的人工蛛网。如图3所示,离基站节点“近”的蛛网的中心节点(例如h),可以直接与基站通信,处在“中间”位置的蛛网的中心节点需要以“近”的中心节点为中继与基站通信,同样,处在“较远”位置的蛛网的中心节点,是以“中间”、“近”的中心节点为中继与基站通信。基站只要确保每个子网的中心节点能与之可靠通信即可,这样在一定程度上提高单相基站采集数据的效率,降低了网络节点的数量,降低了数据冲突率。
2 电力线通信人工蛛网路由
2.1 人工蛛网组网算法
2.1.1 子网中心点选取算法
研究电力线通信组网可以将低压配电网抽象为图G(V,E),记为G(V(G),E(G))。如图1所示,其中,V(G)为图G的节点集,元素v∈V称为图G的一个顶点或节点,E(G)是V中节点组成的无序对的集合,称为边集。图G每条边的权值vivj,代表任意两个终端节点间的通信距离。这里“通信距离”是指网络内可以直接通信的两个节点所跨过的节点个数,相邻两个节点的通信距离为1。通过Dijkstra算法[20]求出图G中所有顶点间的最短通信距离,并组成距离矩阵D,其元素vivj是图G中顶点vi与顶点vj间的距离,i,j=1,2,,m。
给图G的所有顶点赋权值T(v),代表各终端节点在一定时间段内产生的数据量。对j=1,2,,m,给矩阵D的第j行乘以T(v j),并求所得矩阵的行和。
比较所有行和f(g(v i)),根据Dijkstra算法,其中最大者所在的行对应的顶点即为子网的中心点,故对于某个子网选取中心节点的优化目标函数可表示为式(11)。
2.1.2 组网算法
人工蛛网组网算法如下:
(1)组网开始,由基站节点发送组网广播,在收到该广播的m(1≤m≤n)个节点中,通过中心节点选择算法选择其中一个用户终端节点为第一个蛛网的中心节点h,由节点h对剩下的m-1个节点分配逻辑ID,直到所有m个节点均获得逻辑ID为止。
(2)第一个人工蛛网组网完成后,基站向节点h发送指令,由节点h再次发送组网广播,设有k(m≤k≤n)节点收到节点h的广播,剔除掉已经获得逻辑ID的m个节点,在剩下的k-m个节点中选择一个与节点h可靠通信的终端节点为第二个人工蛛网的中心节点l,重复步骤(1),直到所有k-m个节点均获得逻辑ID。
(3)基站以节点h为中继给节点l发送指令,由节点l发送组网广播,重复步骤(1),假设第二个蛛网已经将剩下的所有n-m个节点连通,此时节点l会得到空响应,并把该响应通过节点h传回基站,至此,组网结束。形成了以节点h为中继节点的m-1边蛛网逻辑通信拓扑和以节点l为中心的n-m-1边蛛网逻辑通信拓扑,这样就建立了基站到该单相网络内所有节点的通信路由。
2.2 自动路由协议
假设某单相网络组网完成后由三个蛛网子网组成,路由协议利用这三个子网进行数据包的发送、接收。数据包格式如图4(a)所示,包括帧头、数据源地址、目的地址、子网中心节点地址、节点层数,分层标志位、节点数据及帧尾。其中,帧头、帧尾用于区分数据帧的起始和结束;数据源地址为源节点的地址标识,为基站,各子网中心节点地址;目的地址为目的节点的地址标识,本文均设置为基站地址;子网中心节点地址为各个子网的中心节点地址标识,是各周边节点发送数据的目的地址;节点层数为网络内组成的子网个数,与分层标志位作比较;分层标志位用于判定节点所在子网及数据包来源,同时,防止发送到基站的数据包被反复广播,提高数据处理效率。数据传输流程图如图4(b)所示。数据传输开始,设置所有节点的初始化节点层数为3,分层标志位为0,基站地址为0。数据传输开始,基站广播分层标志位为0的数据包,只有子网1内的节点收到数据包,判断数据源地址是否等于基站地址,如果是基站地址,则创建新的数据包,包括选取中心节点地址,数据源地址设置为该子网的中心节点地址,目的地址设为基站地址,分层标志位设置为1,节点层数与分层标志位相等,添加节点数据。子网1的周边节点将数据包发给中心节点,中心节点处理完所有数据包后,将其发送至基站节点。基站收到来自子网1的数据包后,进行记录。然后,子网1的中心节点广播请求数据包,这个数据包会被子网1内的周边节点、子网2的所有节点收到。子网1内的节点收到数据包后,判断数据包节点层数与分层标志位是否相等,相等则结束传输。子网2的节点收到子网1的中心节点广播数据包后,首先判断数据源地址是否为基站地址,如果不是,再判断节点层数大于分层标志位,子网2内的所有节点创建新的数据包,与子网1创建数据包过程一致,数据包的节点层数与分层标志位相等,设置为2。子网2的中心节点处理完周边节点数据后将其发送至子网1的中心节点,子网1的中心节点比较本节点数据包的节点层数小于收到数据包的分层标志位,则将该数据包发送至基站,至此完成子网2的数据与基站之间的通信。然后,子网2的中心节点广播请求数据包,被子网1,子网3的节点收到,子网1的周边节点收到该广播数据包,结束程序,中心节点收到该数据包将其发送至基站。子网3的节点判断收到数据包的节点层数大于分层标志位,创建数据包。节点层数与分层标志位相等,设置为3。子网3的中心节点处理来自周边节点的数据后,以子网2,子网1的中心节点为中继节点,将数据发送到基站,至此完成所有节点与基站的通信。子网1到子网3的网络内数据采集以及数据广播是依次进行的,例如,子网1数据采集完成后,将数据发给基站,中心节点h向子网2的中心节点发送广播,子网2开始数据采集与发送,依次类推。同一时间段内,只有一个子网占用信道,进行数据采集与传输,在一定意义上减少了节点数量。
利用三层网络进行数据包的产生,发送过程如图5所示。在每一层子网中都创建新数据包,其中源地址设置为其所在子网的上一层子网的中心节点/基站地址,目的地址均为基站地址,子网的中心节点把数据发送到上一级子网的中心节点/基站,同时对下一层网络进行数据广播。这种将大型网络分割成若干小型子网的数据传输方式在理论上有利于降低总线型信道的数据冲突率,提高信道的利用率和系统的效率。
2.3 终端节点建模
在本文中,不考虑用户终端节点的物理故障造成的通信失败。假设在信道环境良好的情况下,每个用户终端均工作良好,只有信道环境的改变,造成用户终端节点的工作状态的改变。因此,可以应用两状态马尔科夫模型来表征由于信道环境改变造成的用户终端节点通信状态的变化情况[21],仿真观察故障节点对系统的影响。如图6所示,“良好”“故障”表示用户终端节点的两种工作状态。“良好”代表终端节点可以与其所在子网的中心节点直接通信,“故障”代表终端节点不能与其所在的子网中心节点通信。本文假设,在一个数据采集周期内,节点的工作状态是不变的。在一个采集周期结束后,由于信道状况的改变,“良好”“故障”两种状态才发生改变。Pg和Pb分别定义为节点在一定信道状况下处于“良好”和“故障”状态的概率,Pgg和Pgb分别定义为一个数据收集周期后,“良好”状态的节点仍处于“良好”状态或是变成“故障”状态的概率,Pbb和Pbg也是类似的定义。式(12)~式(15)为状态变换的数学表达式。
3 仿真与试验研究
3.1 仿真环境
本文根据实际低压配电网的配电环境,在半径50 m范围内分布14个用户终端和一个基站节点,以PC机为仿真硬件平台,以Opnet14.5为编译和仿真环境。在不考虑数据处理延时的情况下,具有2个子网的网络结构就可以表示路由协议的有效性。假设在仿真时间内所有节点组成的两个6边形蛛网结构不发生改变,并依据式(11)确定每个子网的中心节点。由于中心节点到每个周边节点的“距离”都为1,则此处的中心节点为与各个周边节点通信流量最大的节点。图7所示为组网完成后的网络拓扑,subnet_0代表基站节点,subnet_1_0和subnet_2_0为各自子网的中心节点,其他节点为终端节点,信道传输速率为1 000 bps,每个数据包大小为24 bits。对采用新的蛛网路由协议后的信道数据冲突率,吞吐量,信道利用率等参数与采用CSMA协议下的相关参数进行仿真对比分析。本文设定一个数据采集周期为600 s,所有的仿真时间设定为3 000 s,即5个数据采集周期。
3.2 试验结果分析
从马尔科夫模型两状态表达式(12)~式(15),可以明显看出在Pg,Pb,Pgg,Pgb,Pbb,Pbg六个变量中,只有Pg和Pgb为独立变量,其他参数均可由这两个参数来表达。因此,分析这两个变量来观察新型重路由算法的时间特性和工作效率。由式(15)可知Pgb=(Pb Pg)·Pbg,由于0
图9所示为gP=0.9情况下的信道状态仿真结果。图9(a)为两种协议的吞吐量仿真结果,图9(b)为与之相对应的链路利用率的仿真结果。从仿真结果中可以得出,CSMA协议下的信道数据冲突率比较高,信道吞吐量及利用率均比较低,相同条件下,CWRP协议由于数据冲突率很低,信道的吞吐量与利用率均有大幅提高,这对电力线通信的上层应用,保证服务质量是非常重要的。
4 结论
(1)本文从提高低压配电网通信可靠性角度出发,提出了基于人工蛛网的电力线通信组网拓扑,并建立了相应的蛛网数学模型,为以后针对蛛网模型的相关研究提供理论基础。
(2)建立基于蛛网的组网结构,针对该结构,首次提出中心节点选取算法,详细叙述组网过程,建立新的自动路由协议,理论分析表明该路由协议在降低数据冲突率,提高信道吞吐量,信道利用率方面有很大优势。以两状态马尔科夫模型表征通信节点,具有代表性。
(3)与CSMA协议在数据冲突率,信道吞吐量,利用率方面进行仿真对比结果显示,新的CWRP协议在以上方面表现均大幅度优于CSMA协议,证明了理论分析的正确性,以及CWRP协议的优越性,在提高通信可靠性方面具有一定的意义。
摘要：针对低压电力线载波通信可靠性低的问题,提出了人工蛛网通信网络模型,并建立了相应的数学模型。将三相配电网的MAC层转化成由多个人工蛛网组成的逻辑拓扑。详细叙述了组网过程,提出了中心节点选取算法,制定了自动路由协议。以两状态马尔科夫模型表征用户终端的工作状态,模拟实际中由于信道变化产生的终端节点通信失效。针对数据冲突率、通信流量、链路利用率等方面进行建模仿真对比实验,仿真结果表明新的组网方式及路由协议在提高电力线载波通信可靠性方面具有较大优势。
扫一扫微信支付