颜洲

（滁州职业技术学院，安徽 滁州 239000）

智能公交系统自组网路由算法研究与设计

颜洲

（滁州职业技术学院，安徽 滁州 239000）

为提高智能公交系统运行效率，利于人们高效出行。通过对智能公交系统的特点、静态路由算法、动态路由算法和基于Zig-Bee技术的智能公交系统无线自组网路由算法的分析，提出了基于AODV算法改进的AODVjr自适应路由算法。

路由算法；AODVjr；智能公交系统；无线自组网

随着社会快速发展，对智能公交系统安全、快捷、高效、舒适提到新高度。对智能公交系统的数据处理、数据传输、数据更新和数据维护提出了新要求。而这些性能的提高是由路由算法的运行效率来决定。

1 路由算法

1.1 静态路由算法

静态路由算法［1］是根据网络的拓扑结构或链路的状态，由网络管理人员手工配置的路由信息，其不随网络结构的改变而改变，也不随网络流量的变化而变化。静态路由算法一般用于网络结构比较简单，不易改变的网络。其优点是简单、高效尤其是网络安全性和保密性比较高，它不像动态路由算法不停地交换路由表，从而可以通过分析得出网络的拓扑结构和网络地址等信息。其缺点是不能对网络的结构变化，做出及时的反映，而要由网络管理人员对其进行修改，这势必要求网络管理员了解整个网络的拓扑结构，但这是不可能的，特别是对一些复杂的大型的网络而言，整个网络的拓扑结构会经常变化，人为的调整不可行，而且会导致网络长时间不能使用。所以说静态路由算法只适合于网络结构比较固定、比较小的网络。

1.2 动态路由算法

动态路由算法［2］是根据网络拓扑结构和网络流量的变化，动态调整路由表，然后通过互联的路由器传递信息。当一个路由器收到另一个路由器发来的路由更新信息，其自动更新自身的路由表，实时的根据网络变化做出调整。其优点是路由节点增加或减少，不需要网路管理员做出调整，相比静态路由算法减轻了网路管理人员工作负担；当网络拓扑结构发生变化时，网络协议可以自行进行处理和调整；网络扩展性比较好，网络设备增加比较简单，且配置简单不容易出现错误。缺点是路由选择时占用更多资源（网络带宽、CPU时间和内存），相比静态路由算法其网路延时增加，对网络设备性能要求增加。

2 智能公交自组网路由特点分析

智能公交系统ZigBee网络与普通ZigBee网络的区别在于，智能公交系统站台的固定性与公交线路的复用性。智能公交ZigBee网络路由特点：

（1）静态节点。在智能公交系统中部分路由节点和站台节点是很少变化，可以使用静态路由算法。在使用中由于路由设备增加或者减少，有时会出现设备损坏，这样就会出现路由变化，但这种情况出现的概率比较小。

（2）多条转发。一个城市有多条公交线路，而每一条公交线路分为上行线路和下行线路，每条上、下行线路都拥有几十个公交站点。这些公交站点的数据通过路由器全部汇总到线路采集节点，而这个节点一般位于线路的结束站点，这对距离比较远的站点数据就要经过多次转发才能到达线路采集节点。

（3）路由选择可控。在ZigBee网络中路由节点会受到距离的限制，只能与周边的路由节点进行通讯。在智能公交系统中站台沿道路两侧分布，可以认为同一条线路两边站台路由设备是互相备份的关系。它们只能通过最短距离的路由节点和备用节点进行通讯。可以说此ZigBee网络路由选择是可控、可知的。

（4）路由节点复用。在城市中公交线路是交叉存在的，由于路由节点的复用性，它隶属于不同的公交线路，承担着不同线路的数据转发和判断数据属于哪个节点，进行有效转发。

（5）无能耗影响。在智能公交网络中，数字站台节点、数据采集节点和调度中心的供电全部由供电公司负责，车载设备的用电由汽车发动机提供。而不像其他ZigBee网络，其供电由电池供电，这样就避免了能耗的制约，从而不将能耗作为重要因素进行考虑。

3 智能公交系统自组网路由算法比较分析

ZigBee网络层主要负责车载节点的接入与脱离、网络路由选择和数据传递等工作。但其自身没有组网路由协议，这就需要用户自行选择组网方式。

3.1 Cluster-Tree算法

智能公交系统是由站台节点和采集系统节点组成，站台节点和线路采集节点的位置属于固定不变的，因此可以认为智能公交网络拓扑结构是稳定的，不易变化的。从这点可以看出，智能公交系统网络可以采用静态路由方式。

而Cluster-Tree算法［3］就是一种静态路由算法。其通过网络协调设备建立起新的网络结构，这种结构为簇树状，适用于小范围移动节点或者节点静止的场合。簇树网络主要由FFD设备和部分RFD设备组成。一个FFD设备可以连接多个FFD设备或者RFD设备，但一个RFD设备只能连接一个FFD设备，所有RFD设备一般用于叶子节点处。在一个个域网（PAN）中，首先为协调设备设置一个簇头，其值设置为0，再接入一个无标识的协调设备，通过广播方式发送信标，建立一个簇网络。

当备用设备在接收到信标时，协调设备通过信息判断，来决定是否加入。如果同意，则该节点作为一个子节点加入网络，其所有子设备也跟随父设备一起加入。当一个簇网络组网成功后，通过另外一个网络的簇头建立一个新的活动节点，让其他节点加入。簇树网络结构，如图1。

图1 簇树网络结构

Cluster-Tree算法是由动态加表簇树算法演变而来，常见的路由算法有LEACH算法和TEEN算法。

3.2 AODVjr算法

在智能公交系统网络中，站台节点和线路采集节点比较多，通信量比较大；公交线路的部分线路重叠交叉，部分站台节点被多条线路复用，这些重叠的站台节点由于要大量转发数据，容易造成网络局部拥塞；还有由于线路改动、站台节点损坏失效、站台增减，从而导致网络拓扑结构改变。以上这些问题都会对网络传输产生影响，因此要根据具体情况调整路由表，而调整静态路由表势必增加网络开销，导致延时过长，增加网络不稳定性。因此，可以采用动态路由算法。

而AODVjr［4-6］算法是通过对AODV算法优化形成的，其具有功率小和实用性强等特点，保留了AODV算法的基本功能。AODVjr算法路由包由两部分组成：路由请求包（RREQ）和路由回复包（RREP），通过这两个包来实现查找和记录功能。当节点收到数据包后，通过查询路由表来判断是否存在最短路径，如果不存在最短路径。则发送路由请求包，寻找最短路径，当路由节点收到目的节点发送的路由回复包，说明存在一条最短路径，数据包再沿这条路径传送到目的节点。在算法中为了避免出现无效包和循环问题，只有目的节点能发送路由返回包。AODVjr算法请求与回复（其中A为源节点，H为目标节点），如图2。

图2 AODVjr算法请求与回复

3.3 两种路由算法比较分析

Cluster-Tree算法优点在于它的覆盖范围广，查找节点比较简单、快速。通过一个个簇网的建立，降低了网络的功耗和信息冗余；可以减少网络路由和数据处理开销，同时可以控制网络中部分节点的传输范围。其缺点是不能适应网络拓扑结构变化和不能选择网络最短路径，从而产生大量能量消耗。

AODVjr算法具有灵活高效路由查找功能，能快速适应动态链路环境，具有处理时间短，内存占用少，具有自我学习和发现拓扑能力。因其路由表不停地维护会产生延时，这样就会产生广播风暴。通过吸取两种算法的特点，提出基于Cluster-Tree和AODVjr的组合路由算法。这种算法动静结合，有效地解决了网络结构相对稳定和拓扑结构变化带来的一系列问题，如图3所示。

图3 Cluster-Tree+AODVjr组合路由算法数据传输图

当A节点发送一个数据包给E时，由于A节点为RFD类型，所以它只能将数据传输给B节点，当B节点收到数据将其存储，然后通过网络发送路由请求包，来查找到E点的最短路径；找到后由节点E发送路由回复包，把B到E的最短路径E-D-B传输给B。节点B收到路由路径后，把存在B的数据，沿B-D-E传输给E。E收到数据后，沿E-D-B-A发送确认包给A，当A收到确认包后，整个通信过程即结束。

4 AODVjr自适应路由算法设计

在网络中，如果一个节点具有路由发现表功能又具有路由表功能，则认为其具有路由能力。在智能公交系统中路由设备和线路信息采集节点都具有此功能。如果路由设备或者路由节点在其维护的路由表中存在一个能到达目的节点的路由记录，或者其正在尝试建立一个路由线路并记录在路由表中，认为其具有路由表能力。

在网络中路由设备或者协调设备，都应具有维护路由表和路由发现表的功能。路由表中的路由路径都是长时间保存的而路由发现表的路由路径一般只是临时存储。

4.1 路由表

路由表是指由路由设备或者协调设备存储到达特定网络终端路径的表，主要用于路由转发。

表1 路由表条目

Destination address：目标地址；

Status：路由信息；

Many-to-one：多对一路由标识；

Route record required：路由标识；

Group ID flag：目标地址是一个组ID；

Next-Hop address：下一节点网络地址。

4.2 路由发现表

路由发现表只存储一些临时性的由路由设备或协调设备产生的路径信息。

表2 路由发现表条目

Route request ID：路由请求信息ID；

Source Address：路由发送者源地址；

Sender Address：源节点地址到目标节点网络地址的最短路径和此路径路由请求标识符；

Forward Cost：发送节点到目的节点路由消耗量；

ResidualCost：当前路由节点到目标节点路由消耗量；

Expiration Time：发送节点到路由发现终止的时间［7］。

协调设备和路由节点具有路由能力，所以智能公交网络具有以下功能：具有本地和端到端路由修复功能；具有数据转发功能；具有路由发现功能和路由成本计算功能。另外，路由节点和协调设备还具有以下路由功能：代表上层和其他路由节点启动路由发现；代表其他路由节点和端到端路由修复功能；及时更新路由表。

基于ZigBee技术的智能公交系统存在着三类节点：线路采集系统的协调点、数字站台的路由节点和车载节点。在这三类节点中，把线路采集系统的协调点路由、数字站台路由节点分为一类，把车载节点“路由”分为一类。车载节点“路由”是指车辆在行驶过程中，根据存储路由表不停地加入下一个路由节点网络，同时脱离上一个路由节点网络，车载节点路由表实际上就是车辆行驶在这条线路上经过的站台节点和协调点的一个顺序表格。

4.2.1 AODVjr路由算法

在城市运行的公交线路站台节点成对称线状分布，这样站台路由节点也就是成对称线状分布于线路两侧，如图4。

图4 站台路由节点分布图

由于ZigBee网络中设备传输距离的限制，在站台节点数据传输时，如果某一个站台节点出现故障，路由设备会选择其他路由节点进行数据传输。

图5 路由节点数据流

例如，如图5所示，可与X3路由节点有直接数据连通的有X2、S2、S3、X4、S4等五个路由节点。这时如果下行线路X1要传输数据给线路上的X6，就可以发现有多种路由线路可供选择，数据可以按照X1、X2、X3、X4、X5、X6线路进行数据传输，也可以按照X1、X2、X3、S3、S4、X5、X6线路进行路由传输，还可以按照X1、X2、X3、S3、S4、S5、X5、X6线路进行路由传输，还有其他路由线路也可以进行数据传输。

而根据成本要求，一般选择最短最优路径进行数据传输。上面的例子如果按照路由成本最小选择，则最短路由线路为X1、X2、X3、X4、X5、X6。因此，根据最小路由成本，智能公交线路路由节点数据流，如图6所示。

图6 AODVjr路由算法示意图

路由节点S1-S7这一侧线路为这条公交线路的上行线路，路由节点X1-X7这一侧则为下行线，这两条线路为这条公交线路的最短路由线路。数据在流动方向、转发方向与公交车运行的方向一致，说明其流动方向是可定的有规律的。因此，这样的路由可称为“定向路由算法”。

定向路由是指按照既定的路由线路进行数据传输，在智能公交系统中公交车运行的方向是既定的，所以路由线路也是既定的。路由线路上的路由节点可以进行通讯，在通讯过程中如果此节点不是目的节点则它只有路由转发功能。如路由节点X3收到一条数据要发给路由节点X6，那它只能沿X3、X4、X5、X6进行数据传输。

4.2.2 AODVjr自适应路由算法

智能公交系统在使用时，可能会出现个别节点故障问题，这时可以使用AODVjr自适应路由算法。其主要是路由节点发生故障时，路由选择另一条路径，但是以定向路由为基础的路由方式。

图7 AODVjr自适应路由算法图

如图7所示，当公交线路在运行时，下行线路X4站点出现故障，将导致X4这个站点路由节点失效。由于X4路由节点失效，公交线路在数据传输时，就必须选择其他路由节点进行数据转发。如果有一组数据要从路由节点X2发送到路由节点X6，当整条路由线路正常时，按照最短路径原则，其路径为X2、X3、X4、X5、X6，但路由节点X4出现故障，不能通信。那只能进行路由转发，可以路由转发的路由节点有三个，分别为S2、S3、S4，但按照最短路径原则，其路径则为X2、X3、S4、X5、X6，这条最短路径则借用了和X4对称S4这个备用路由节点。但这样的路由选择又存在一定的问题：一是没有指定路由选择时的先后顺序，会导致公交线路数据流出现混乱；二是路由节点X3按照最短原则选择了S4，但由于两个节点在公交线路的两侧，并且两个节点不相邻，间隔距离较远，这样会导致干扰增加，数据传输质量不高。

因此，可以规定当数据在传输时，某个节点发生故障，其故障节点的上一个节点进行路由选择时，首先选择这个节点对面一侧的路由节点，进行路由转发工作；只有当这个节点的对面节点也发生故障时，才可以选择故障节点对面这个节点进行路由转发工作。

在公交系统运行中有很多站台是属于不同线路在使用，这时站台路由节点就是复用的，其在传输数据时就要根据目的地址属于哪一条线路进行路由转发，如图8所示。

图8 公交线路路由节点复用时路由算法

在上图中大家可以发现出现复用的路由节点有A1、A2、A3、A7、A8、A9等六个节点，这六个节点分别属于线路1、线路2和线路3，它们分别保存着每一条线路的路由表，以备路由选择时使用。线路1的上行路由线路为A7、A8、A9、B5、B6、B7；线路2的上行路由线路为A7、A8、A9、B11、B10、B9、B8；线路3的上行路由线路为A7、A8、A9、A10、A11、A12。

4.2.3 自适应定向路由的实现

图9 智能公交系统自适应定向路由流程图

如图9所示，智能公交系统在运行时，某个路由节点接收到一组帧数据，首先，判定是否为广播帧，如果是则广播该帧，则接收；如果不是，判断其路由目的地址，是本路由节点地址，交由节点上层进行处理，不是，则通过路由表查询目的地址，进行路由转发；如果路由表没有其对应的路由线路，则路由节点进行路由查找工作。当公交站点为多条线路所使用时，说明路由节点为复用，在转发路由数据时，首先判断其属于哪一条公交线路，然后再选择路由节点进行转发工作。当数据帧为路由节点同侧时，则判定下一个路由节点工作是否正常，如果正常，就进行转发；如果数据帧为路由节点异侧时，则判定异侧路由节点工作是否正常，如果正常，就进行转发；如果路由线路同侧的下一个路由节点和异侧的路由节点都出现故障，则判定异侧下一个路由节点进行转发，或者选择其他可用路由节点进行转发。

5 结语

本文通过分析静态路由算法和动态路由算法的优缺点，然后提出动静结合的智能公交系统自组网路由算法。通过对两种路由算法进行比较分析，针对公交系统的特点、动态路由策略和数据传输的特殊要求，根据AODV路由协议，提出了具有实时性、可靠性和灵活性的自适应路由算法AODVjr。

［1］静态路由与动态路由的概念及实例说明［EB/OL］.http://net.zdnet.com.cn/network_security_zone/2008/0514/860657.shtm l.2008.

［2］胡九川，刘鸿飞，等.稳定服务质量水平的动态路由算法［J］.通信学报，2004，25（08）：145-149.

［3］邹国霞，李燕.ZigBee中Cluster-Tree路由算法改进研究［J］.制造业自动化，2011，33（13）：110-112.

［4］陈林星，曾曦，等.移动Ad Hoc网络：自组织分组无线网络技术［M］.北京：电子工业出版社，2006.

［5］IETFRFC 3561，Ad Hoc on-demand distance vector（AODV）routing［S］.2003.

［6］PerkinsC.E.and Royer E.M..Ad-hoc On-Demand Distance Vector Routing［A］.Second IEEEWorkshop on Mobile Computing Systemsand Applications［C］，1999，2.

［7］耿萌.ZigBee路由协议研究［D］.郑州：中国人民解放军信息工程大学，2006.

Research and Design of Rou ting A lgorithm in In telligen t Transportation System

YAN Zhou

（Chuzhou Vocationaland TechnicalCollege，Chuzhou，Anhui，239000，China）

In order to improve the operation efficiency of the intelligent public transportation system，it is helpful for people to travel in high efficiency.We through the characteristics of the intelligent transportation system static routingalgorithm and dynamic routing algorithm based on ZigBee technology and intelligent transportation system ofwireless ad hoc network routing algorithm analysis，proposed AODVjr adaptive routing algorithm based on improved AODV.

Routingalgorithm;AODVjr;Intelligentpublic transportation system;Wirelessad hoc network

TP393.04

A

1008-9659（2016）04-0049-08

2016-11-07

颜洲（1981－），男，安徽滁州人，讲师，主要从事计算机网络、智慧校园虚拟网实训设计方向研究。