图 1 城市交通网络汇聚点与端口权值
67 0.65 67.2
45 0.65 20.3 1 2 45 0.65 20.3 3 designatedport 45 0.65 20.3 4 designatedport
portroles
2 算法实现
根据上节提到的向量组优先级比较以确定最终 的汇聚端口优先向量，根据端口优先向量的内容确 定端口角色，这样可以实时计算整个城市交通网中 存在一条通过花费最小的道路。当道路发生堵塞触 发重新计算进程，从而找到其他备份的最优道路。 下面以一实例说明：如图值分别为： 0.65， 0.97，0.86和0.78。以第二个汇聚点为例，其有四个 Port连接到城市交通网，67.2代表第二个端口的花费 值为67，其余汇聚点和端口均为此表示方法。使用 向量优先比较，以下计算为第二个汇聚点，权重值 为0.97的端口角色。
alternate port , alternate 1port 。
1 拥堵分流算法
1.1 算法概述 本算法的思想就是要在整个城市中形成连接到 各个地点的树形道路， 各个地点的道路连接点处 （道 路汇聚点）通过交通流量采集设备获得道路流量信 息，道路汇聚点通过信息数据包(IDU)的交换来进行 计 算 ， 选 定 城 市 交 通 网 中 的 根 汇 聚 点 （ Root Convergence Point ） i 和 指 定 汇 聚 点 （ Designated Convergence Point ） ，确定道路端口的角色是根端口 （ Root Port ） 、指定端口（ Designated Port ）或者备 用端口（alternate Port） 。经过计算后，生成了一个 无环路的“树”型交通通行率最小的道路结构。 1.2 算法信息数据单元（IDU）的构成 城市交通网络内各个道路汇聚点（Convergence Point）根据每个道路端口优先级向量决定每个道路 端口角色。 这些角色分别为： root port ,designated port ,
root pathcos t vector

Pr iority
0.65 0.65 0.78 0.86
45 67 100 100
0.65 0.65 0.78 0.86
20.3 1 67.2 2 100.2 3 100.1 4
分析：经过以上算法，算出权值0.97的汇聚点的 端口优先向量，端口1和2的优先向量表明，根汇聚 点和上游汇聚点均为0.65，由于端口2到根汇聚点开 销比端口1大，所以端口2为替代端口最为端口1的冗 余。端口3、4的port priority vector来自designated vector，所以为指定端口。 当计算完成后可以定时重复运算，通过道路流 量监测在只改变端口拥堵因子值的条件下重新计算 单向通道花费值，找到最优的覆盖所有汇聚点的道 路。其他汇聚点以相同算法运算，这样在城市交通 网络总形成了一条单向最优道路。如图2所示，其中 实线为最优道路，虚线为拥堵道路。
[2]de Sousa. Improving Load Balance and Resilience of Ethernet Carrier Networks with IEEE 802.1D Spanning Tree Protocol [Z]. Mauritius Islands: 5th Int Conference on Networking,2006. [3]ZHANG Yin-di,LI Ka-i tai.The error estimates of the characteristic finite element method for nonlinear ad-vection-diffusion equation [J]. Journal of Changpan University: Natural Science Edition, 2004, 24 (6):106-110. [4]王辉. 一种基于MSTP的负载均衡算法设计[J]. 电子设计工程，2011,19(215):83-86. [5]吕俏,刘启文,石冰心. STP协议原理的算法与实 现[J]. 华中理工大学学报，2008,28(1): 38-41. [6] G Ibanez, Garcı-Martı, Azcorra. Bridges: Scalable, self-configuring Ethernet campus networks [J/OL]. Computer Networks, 2008, 52 (3): 630–649. [7]关积珍,郑长青,朱雪良,等.北京奥运交通诱导VMS 信息发布研究[J].交通运输系统工程与信 息,2008,8(6):115-120. [8]MEI Zhen-yu,XIANG Y-i qiang,CHEN Jun,et al.Op-timization method of configuration of traffic flow guid-ance information board in urban [J]. Journal of Traf-fic and Transportation Engineering, 2007, 7 ( 5 ): 88-92.
（2） 从root path cost vector中找到最优向量作为 指定汇聚点向量，再根据根汇聚点的权值和接收端 口的拥堵因子值进行更新，生成指定端口。
root pathcos t vector 0.65 0.65 0.78 0.86 45 67 100 100 0.65 0.65 0.78 0.86 20.3 1 designated vector 67.2 2 0.65 45 0.65 20.3 1 100.2 3 100.1 4
0，否则就为其他汇聚点所收到的 IDU 的 Root Path Cost(receive)值与收到该配置消息的道路端口拥堵因子 (Port Cost)之和。拥堵因子 Root Path Cost 计算公式 如（2）所示： Root Path Cost =Root Path Cost(receive)+Port Cost(receive) （2） （3） 确定指定汇聚点和 Designated Port：一条 道路路径分别连接到两个不同的汇聚点，根据公式 （1）和公式（2）的计算结果，Root Path Cost 最优 先，即拥堵因子值最小的汇聚点为指定汇聚点。一 条道路链路中所属指定汇聚点的端口为指定端口 （Designated Port） 。 （4） 确定根端口（Root Port）和替代端口 （Alternate Port） ：非根汇聚点上接收的最优五元向 量组的端口为根端口。除了根端口和指定端口，其 余的端口都是替代端口，这样就构成了一个逻辑树 形结构的最低拥堵交通网络。
关键词：城市交通；拥堵分流；向量优先级 中图分类号:TP 393.1 文献标志码：A
引言
随着城市交通网络的建设和应用，城市交通道 路越来越多地连接城市不同的地点。城市交通网的 特点是冗余性设计被采用，即通过多条链路连接同 一地点形成网络环路，确保某条链路拥堵后城市交 通网络仍能保持通畅。这些冗余链路对交通管理带 来一个新问题，即当某条或者若干条城市交通链路 发生拥堵，如何选择若干条交通量最小，或者通行 效率最优的道路来连接整个城市，即能保证城市正 常的交通运力，又能缓解拥堵路段的压力进行分流， 有效提高了道路运行效率。
驶人员的经验，准确率很低。本文提出一种实时计算道路信息流并选择最优道路进行分流的算法，具有实时性、智能化高的特 点。该算法设计了一个五维向量作为输入信息，采用向量组优先级比较的方法，通过对道路端口计算来生成最优化路径。本文 最后给出一个实际计算实例，拥堵分流算法生成其他最优备选道路，从而有效的实现了拥堵分流，使城市交通性能得到优化。
（3）在更新过的端口优先向量组中，1端口与2 端口的向量都来自其本省的拥堵因子累积向量，端 口1的拥堵花费为45，而端口2为67，端口1由于端口 2为最优路径端口。端口角色被定义后，port priority vector参与下一轮运算。
port priority vector 0.65 0.65 0.65 0.65
（1）第二个汇聚点各个道路端口接收的道路对 端端口发来的五维消息向量组与初始化时本汇聚点 各个端口的优先向量，根据优先级得到根汇聚点为 权值是0.65的汇聚点和各个端口的更新累积拥堵因 子值的端口向量组：
0.65 0.65 0.78 0.86 0 0 0 0 0.65 0.65 3.84 0.86 20.3 67.2 100.2 100.1 1 0.97 2 0.97 3 0.97 4 0.97 0 0 0 0 0.97 0.97 0.97 0.97 45.1 67.2 100.3 100.4 1 2 3 4
（1）城市交通网络中汇聚点不是根汇聚点，且该汇 聚点的某个端口优先向量来源于根汇聚点，那么该 端口是根端口（root port）。 （2）道路路径端口优先向量来源于指定向量，则该 端 口 是 交 通 网 络 中 的 道 路 指 定 端 口 （ designated port） 。 （3）城市交通网中，除了根端口外，汇聚点某个端 口的端口优先向量是从其他汇聚点接收来的，该端 口是替代端口（alternated port） 。 1.3 向量组优先级比较 每个道路端口将参与运算的关键参数字段构成 一个五维向量： { Root Convergence Point, Root Path Cost , Designated Convergence Point, Designated Port , 汇聚点各个道路端口通过比较彼此交换的 RcvPort }， IDU 包中的五元向量组进行优先级确定，优先级比 较顺序是从左至右，如果靠前的向量值小，则表明 为优先向量组。五维向量组的比较过程如下： （1） 计算 Root Convergence Point：在道路交 通网络中各个汇聚点首先推举一个汇聚点作为树形 道路的根汇聚点，推举依据是各个汇聚点的优先值， 优先值的选择根据汇聚点在城市交通中重要程度和 设计标准选择，值范围为[0，1]，计算公式如（1） 所示： Root Convergence Point = Priority (Convergence Point {n}) （ 1） （2） 计算累积拥堵因子 Root Path Cost：如果 汇聚点本身是根汇聚点，则到根汇聚点路径开销为