一种用于火灾现场的最小代价路由算法

摘 要:随着社会经济的高速发展和网络技术的不断更新,网络设计者面临的问题尤为突出。本文首先分析火灾呈不断上升的趋势,进一步构建火灾现场Ad hoc临时通信网络,并结合传统路由协议,再引入Ad hoc网路中最小代价路由算法的设计原理、路由选择和配置,最终通过实施最小代价路由算法有效提高网络的综合效能,实现网络的最优化配置方案。

关键词:消防 Ad hoc网络 路由算法

中图分类号: TP39 文献标识码:A 文章编号:1007-3973 (2010) 05-096-02

随着社会经济的高速发展,建筑、人口越来越集中,火灾呈不断上升的趋势,危害也越来越大。火灾不仅给人们造成巨大的人员伤亡和财产损失,同样还直接威胁到消防员的人身安全。因此,在发生火灾后如何快速,行之有效开展消防工作,并且在灭火救援过程中,保障消防人员的人身安全,刻不容缓。在发生火灾后,如何利用消防通信网络快速布置消防工作,己经做了较多的研究。但是,大部分的研究都集中在接到火警后如何产生消防预案上,而在火灾现场辅助消防员执行消防工作的移动通信辅助网络依然较少。根据对消防实际情况的调查,发现消防员执行工作时存在整个火灾形势难以获取、通信手段落后、工作环境恶劣三个主要问题。在分析上述三个问题和消防员的自身需求后,我们利用 Ad hoc能够快速组成应急通信网络的特点,提出了一种能够辅助消防员在移动情况下临时通信的路由算法。该算法能减小传输延时,提高带宽利用率和传输效率,降低能耗,在设计优化算法时拓展原协议的功能。

1 构建Ad hoc网络模型

移动Ad hoc网络,是一种多跳、临时、无中心的自组织网络,不需要任何基础设施(包括基站、接入点等)支持,它由一组带有无线通信收发装置的移动终端节点组成,每个终端既是数据接收点同时又是路由点需要转发其它终端节点数据,节点之间的通信方式既可以采用单跳又可以采用多跳方式实现,网络中每个终端可以自由移动、地位相等。总之Ad hoc网络是一种可以在任何时候、任何地点快速构建起来的移动通信网络,它在军事侦察、抢险救灾、环境保护及商业应用中发挥着越来越重要的作用,如今已经成为移动通信技术向前发展的一个重要方向。

针对火灾现场的实际情况,以无线网络中的Ad hoc网络作为构建的网络体系。构建如图1所示的Ad hoc临时通信网络。该通信网络由消防官兵和通信指挥中心组成。如果其中一个需要进行通信的源节点(消防员1)没有一条到达目标节点(消防员4)的有效路由,它便会广播RREQ消息,启动一次路由发现过程。当中间节点(消防员6)收到一个RREQ消息,将转发该路由请求消息直至目标节点。目标节点将选择合适的路由返回路由响应消息,该消息中携带了从源节点(消防员1)到目标节点(消防员4)的完整路由。

2传统AODV路由协议

AODV是一种反应式的按需Ad hoc网络路由算法,AODV协议综合了DSDV和DSR协议的特点。与基于表驱动方式的DSDV协议相比,AODV协议采用了按需路由的方式,即网络中节点不需要实时维护整个网络的拓扑信息,而只是在发送报文且没有到达目的节点的路由时,才发起路由请求过程;与DSR相比,在AODV协议中,由于通往节点路径中的节点建立和维护路由表,数据报文头部不再需要携带完整路由信息,减少了数据报文头部信息对信道的占用,也提高了系统效率。因此,协议的带宽利用率高,能够及时对网络拓扑结构变化做出响应,同时也避免了路由环路现象的发生。但是在AODV协议中也存在一些问题,随着自治系统(AS)规模以及网络路由表的增长,AODV更新所耗费的网络带宽也在不断增长,以及路由选择变化的增长,路由收敛时间也在增长。鉴于AODV的一些独特优点,本文方案选定在AODV协议基础上改进,进一步解决其在应用中存在的问题,使其更好地应用到消防通信网络当中。

3最小代价路由算法的设计

传统的AODV协议以最小跳数作为路由选择的标准,一个节点要发送数据时,若本节点路由表中没有到达目的地址的路由,则向目的地址广播一个路由请求RREQ,每个中间节点收到源节点的路由请求后自动建立目的节点为源节点的反向路由,同时转发路由请求RREQ。目的节点收到第一个路由请求RREQ后沿它收到路由请求的路径发送一个路由回复RREP。AODV协议力求找到一个从源节点到目的节点的最小跳数路由(即最短路径路由)。其路径发现的开销对网络来说是巨大的。如果采用最短路径策略会使得某些节点处于多条路由上,导致发送数据的负荷过重,过早地耗尽电池能量而不能工作,网络也因此而分裂甚至瘫痪。本文在此基础上优化原有的AODV协议,改“最小跳数路由”为“最小代价路由”,并将其应用到消防通信网络中;通过利用OPNET Modeler仿真软件进行网络建模和仿真,并进一步分析、评估网络、测试、改进网络通信协议,以实现优化网络通信性能。

3.1OPNET的基本原理

OPNET作为一种主流的网络仿真软件,为通信网络和分布式系统的建模提供了全面的模拟仿真开放环境[3]。OPNET将通信网络仿真的各个阶段合并在一起,包括模型的设计、仿真、数据的收集和分析等阶段,采用基于离散事件驱动的仿真机制,每当有一个事件出现后时间往前推进,仿真中各个模块之间通过事件中断方式传递事件信息;基于包的通信机制,通过仿真包在仿真模型中的传递来模拟实际物理网络中数据包的流动和节点设备内部的处理过程;采用三层建模机制,最底层为进程层模型,以有限状态机来描述协议,其上是节点模型,由相应的协议模型构成,反应设备特性,最上面为网络拓扑模型,三层模型和实际的网络、设备、协议层次完全对应,具有很好的继承性和可重用性。

3.2算法的基本思想

OPNET中自带的AODV例子中,协议使用“请求/回复”机制来找到一条由源节点到达目的节点的最小跳数路由。然而这一条路径上节点的WLAN数据传输率不尽相同(节点的WLAN数据传输率和节点负荷有关),为了减小传输延时,提高带宽利用率和传输效率,降低能耗,在设计优化算法时拓展原协议的功能,在路由请求和路由回复中添加“路由代价”条目,改“最小跳数路由”方式为“最小代价”路由方式。

设源节点到目的节点的路径上要经过n个节点,将节点的传输代价aodv_cost做如下定义:

传输代价=网络带宽/节点数据传输率

路由代价=MIN{aodv_cost(1),aodv_cost(2),aodv_cost(3),……aodv_cost(n)}。仿真时指定网络带宽为54Mbps(802.11g标准的最大可能WLAN数据传输率)。为了寻找一条最小代价路径,在路由请求机制中更改以下请求环节:(1)发送路由请求RREQ;(2)处理路由请求;(3)目的节点处理路由请求。

4在OPNET中实现优化的路由算法

建立场景min_cost_VS_default0_1,场景大小100m*100m,选择8个节点,1个源节点,1个目的节点,6个中间节点分别组成两条由源节点到达目的节点的路径,发送分组大小服从指数分布,最小分组的大小为1024bit,分组发送间隔为1s。仿真开始100s后开始发送分组,low_cost_node_1～low_cost_node_5数据传输率11Mbps,high_cost_node1数据传输率1Mbps,hello报文周期为1s,hello报文的最大等待时间为5s,场景仿真时间为500s。

由图2所示仿真动画可以直观地观察到:源节点和目的节点间仅有两条路径,路径1(左)跳数为3,路由代价为54;路径2(右)跳数为5,路由代价为4.9。优化前,按原有的基于最小跳数路由方式,源节点和目的节点间通过路径1传输数据;优化后,按优化了的基于最小代价路由方式传输数据,源节点和目的节点间通过路径2传输数据。仿真结果见下图:

由仿真结果可以看出优化后网络延时(如图3)较优化前减小明显,网络的吞吐量(如图4)也有所增大。由图可知,尽管路径1跳数比路径2要小,但是路由代价却大于路径2,说明最小跳数路由并非最佳路由。此外,在实际操作中节点的负荷大时,数据传输速率随之降低,本方案选择一条路由代价小的路由,同时也避免了负荷大的节点长时间处于高负荷工作,起到均衡负载的作用,从而在一定程度上也有利于延长节点的生存时间。

5结语

本文提出用于火灾现场的最小代价路由算法,并结合火灾现场环境进行分析应用。基于Ad hoc网络快速组成应急通信网络,利用OPNET仿真软件建立一个简单的网络,并对优化算法进行性能仿真,通过仿真分析可以看到优化后的算法在网络延时和吞吐量上有了明显的改善。因此,采用最小代价路由算法对辅助火灾现场通信有着建设性意义。

参考文献:

[1]吴君.省级消防通信网络构建方案的探讨[J].消防科学与技 术,2002.

[2]郑少仁,王海涛,赵志峰等.Ad Hoc网络技术[M].北京:人民邮电出版社,2005.

[3] 陈敏.OPNET 网络仿真[M].北京:清华大学出版社,2004.