路径规划典型算法范文

路径规划典型算法篇1

关键字：Dijkstra算法；最短路径；GIS

中图分类号：TP301.6

Dijkstra算法是一种经典的求最短路径的算法。所谓最短路径问题是指：从带权图的某一顶点出发，找出一条通往另一顶点的最短路径。最短路径问题是GIS应用中研究的一个重要内容，在事故抢修、交通指挥、应急管理、GPS导航等应用中都是必要的功能，所以最短路径分析功能一般会作为基本功能集成到GIS平台中，如ARCGIS，SuperMap。多数系统解决最短路径问题采用Dijkstra算法为理论基础，它非常适合在带权有向图中求解单源单目的最短路径问题。

1 经典Dijkstra算法

1.1 算法思想

Dijkstra算法是典型最短路算法，用于计算一个顶点到其他所有顶点的最短路径。其基本思想是，逐步产生最短路径。首先求出从某一顶点出发到其他顶点长度最短的一条路径，然后参照它求出长度次短的路径，依次类推，按路径长度的递增次序，直到计算出该顶点到其他所有顶点的最短路径。

为了实现该算法，设带权图G=（V，E），V为图中顶点的集合，E为边或者弧的集合。设集合S存放已经求出的最短路径的顶点，设集合T为除了S以外的其他顶点，引入辅助数组dist[]，它的每一个分量dist[i]表示当前找到的从出发点到顶点i的最短路径长度。

算法的具体步骤：

（1）初始化：S={V0}；T={V-S}；Dist[j]=Edge[0][j]；j=1，2，…..n-1，n为图中顶点的个数；

（2）求出最短路径长度：dist[k]=min{dist[i]}，i∈V-S；S=S∪{k}；

（3）修改：dist[i]=min{dist[i]，dist[k]+EDedge[k][i]}对于每一个i∈V-S；

（4）判断：若S=V，则算法结束，否则转到（2）；

初始时，S中仅含有初始顶点V0，每次从V-S中取出具有最短特殊路长度的顶点，将其添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。

1.2 算法分析

实现经典的Dijkstra算法需要两个并列的for循环。一个循环用来实现辅助数组的初始化工作，时间复杂度为O（n），第二个for循环是一个二重循环，实现最短路径求解的功能，因为图中所有顶点都要做计算，每个顶点的计算又要对集合S内的顶点进行检测，对集合V-S中的顶点进行修改，所以时间复杂度为O（n2）。算法总的时间复杂度为O（n2），复杂度比较高。

2 Dijkstra算法改进

通过Dijkstra经典算法思想可知，计算从u到v的最短路径时，也计算了u到S中所有顶点的最短路径，但是，S中的某些顶点可能与最终最短路径中的顶点无关，该算法在进行最短路径搜索过程中会涉及到图中所有的顶点，那么图中S的大小直接影响着算法的速度。这直接影响了算法的效率，因为由时间复杂度可看出顶点数量越多所用时间就越长。优化该算法势在必行。

2.1 改进策略

改进的策略用一句话描述就是顶点覆盖，分段进行。通过前面的分析可知，如果能减少算法中集合S中顶点的个数，会减少算法的运行时间。在这借用希尔提出希尔排序的思想，把有向图中的顶点按照某种策略分成若干个小的集合，形成顶点的全覆盖，这样每个集合的数量就比原来少了，但是把他们合起来顶点及关系总数不变，并且要求不同的集合要有一个连接的关键顶点，关键点的确定是计算最短路径的关键。

顶点覆盖划分的方法可根据具体的计算应用决定，比如可以按照区域划分，按关键点划分，按公路、铁路线划分等等。划分的数量不宜太多也不宜太少，应根据实际情况科学分析。划分数量和每个划分中顶点的数量应事宜，划分数量多，重复执行的次数就有可能多；划分的数量少对算法的改进程度不高。确定连接不同集合的关键点和划分策略有关，有时也要进行事先的运算，关键点应该具有这样的性质，是从一个集合区域到另一个集合区域必经的顶点或者就是终点。最短路径的计算结果是每个小集合划分的结果之和得到的。这样改的好处是，既能减少程序运行时涉及的顶点的数量，如果采用邻接矩阵的方式存储带权图，还能节省存储空间。

2.2 算法设计

下面给出改进算法的方法步骤：

（1）根据划分策略，确定顶点所属不同集合Si，i=1，2，3小于等于划分的个数，确定存储表示方法，并建立相应带全图；

（2）把所有关键点放入关键点集合key，并表示关键点所连接的区域信息，并建立拓扑图；

（3）计算关键点集合顶点间的最短路径，并放入专门的数组或数据表中；

（4）计算任意两个顶点间的最短路径，首先判断顶点所属范围，若两个点均属于关键顶点集合，则直接查找步骤四的计算结果数据表，算法执行结束；若属于同一个顶点划分，直接调用Dijkstra算法，转步骤（5），若属于不同的集合，转步骤（6）；

（5）在两顶点所属划分Si范围内，直接调用Dijkstra算法求两点间的最短距离，算法结束；

（6）假定两定点分别属于划分Si和Sj，则两顶的距离等于，u0和v0所属的集合分别为Ti和Tj，那么最短路径的计算有三部分组成，先计算起始结点到与其所在集合Si连接的关键点的最短距离，在计算与Sj相连接的关联点到终点的最短路径，再计算两个关键点之间的最短路径，最后将三部分计算结果相加，即为两定点间的最短路径。

2.3 性能分析

首先该算法是从减少顶点数量的角度对算法进行优化，对经典算法本身的执行没有改动，不论是计算关键结点之间的最短路径，还是计算任意两个顶点之间的最短路径，仍然调用迪杰斯特拉算法，这就保证了算法的可行性。如两个顶点不属于同一区域采用的是分阶段计算最短路径然后相加的方法，减少了计算的复杂性，增强了可理解性和可执行性。

其次关于改进算法的时间复杂度，和顶点集合划分的数量有关。假设带权图中共有n个顶点，有m个顶点集合划分，k为关键顶点的数量。时间复杂度分为以下几种情况：

（1）如果两顶点均属于关键顶点，则只需要到数据表中进行查找，则复杂度取决于关键顶点的数量和查找最短路径所需要的时间。计算关键顶点的复杂度为O（k2），查找路径可以用优化的查找方法；

（2）如果两顶点属于同一个集合划分，复杂度为O（（n/m）2），是没有改进前的算法复杂度的1/m2。

（3）如果两顶点，不属于同一个集合划分，最短路径计算是三部分计算之和，三次调用经典算法，复杂度与第二种情况同，但事件应该略多。

从空间复杂度角度，若采用邻接矩阵的存储表示方法，经典算法需要用n2个存储空间，改进后只需k*（n/m）2，当然增加了存储关键顶点和其最短路径的存储空间，但相比节省的存储空间和优化的时间复杂度，必要的增加还是值得的。

通过对时间和空间复杂度的分析可以看出改进算法可以极大的减少运算量，降低时间复杂度和空间复杂度。

3 改进算法在GIS中的应用

在ArcGIS平台中实现改进算法的应用，在Java环境下利用Arcobject进行二次开发，采用改进的Dijkstra算法思想编写函数，实现最短路径的搜索。

ArcGIS自带的网络分析模块，具有分析矢量数据的功能，只对具有拓扑关系的矢量数据进行分析，所以首先在ARCGIS环境下对地图进行矢量化，然后进行拓扑分析。本文采用的数据是某一地区的地图数据，文件中一共有3572条地理实体记录，共有2826个顶点，通过对地图数据的分析，确定了按照地理区域进行顶点划分的策略，共分成23个区域，共找到72个关键顶点，每个划分的顶点根据地域及关键点的链接，并不十分平均，但是比起总体的数据量，每个集合的规模都小的多。

利用改进算法进行计算时，按照算法思想采用了两个顶点在关键顶点集合、在两个不同顶点划分集合和两个顶点在同一个顶点集合三组不同的数据进行验证。通过和经典的Dijkstra算法运行结果从正确性和运行时间的对比，证明一方面改进的算法进行最短路径搜索的结果和经典算法相同的，另一方面比经典的算法无论从时间上还是从空间上都有一定的提高。如图1所示，两种算法运行时间的对比图。

图1 运行时间对比

4 结束语

本文在分析经典Dijkstra算法的基础上，提出了“顶点覆盖，分段计算”的思想，进行算法的改进。通过对原带权图中顶点进行覆盖划分，减少算法中顶点集合数目，缩小问题的规模，并通过分段计算最短路径以达到降低算法时间复杂度和空间复杂度的目的，经在ArcGIS中二次开发，结果正确实现了预期设想。

参考文献：

[1]殷人昆.数据结构（用面向对象方法与C++语言描述）（第二版）[M].北京：清华大学出版社，2007.

[2]王涛春，齐学梅，赵诚.Dijkstra优化算法及其在电子导游中的应用[J].安徽师范大学学报（自然科学版），2010（33）：525-529.

[3]陈红琳.在ArcGis矢量图中搜寻最短路径的实现[J].北京测绘，2009（02）：16-18.

[4]王华.基于Dijkstra算法的物流配送最短路径算法研究[J].计算机与数字工程，2011（39）：48-50.

[5]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

作者简介：马小雨（1978-），男，河南郑州人，讲师，硕士，研究方向：网络与安全；余建国（1975-），男，河南林州人，副教授，硕士，研究方向：数据库应用及GIS信息管理。

作者单位：河南工程学院 计算机学院，郑州 451191；郑州航空工业管理学院 计算机科学与应用系，郑州 450015

路径规划典型算法篇2

[关键词]机器人；路径规划；A-star算法

中图分类号：TP242 文献标识码：A 文章编号：1009-914X（2016）20-0218-01

1 引言

科学技术日新月异，移动机器人的应用范围越来越广。路径规划是移动机器人实现自主导航的关键技术之一[1-5]。按照移动机器人对环境的认知程度，可以将路径规划分为基于先验信息的全局路径规划和基于传感器信息的局部路径规划。A-star算法是全局路径规划的经典算法之一；然而，传统A-star算法在搜索过程中也存在自身的缺陷，如搜索出的路径不易于机器人运动控制、搜索速度慢等。本文针对复杂环境下A-star算法的缺陷进行了启发函数和搜索策略的改进。

2 A-star算法概述

A-star算法作为一种启发式搜索算法的优势就在于从当前搜索节点搜索下一步节点时，由一个启发函数来引导选择代价最小的节点作为下一步搜索节点。这样减少了搜索空间，提高了效率。A-star算法中代价函数如下：

1.1

上式1.1中，表示从起始点经过节点n到达目标点的最低代价的估计值，它由两部分组成：一部分为，是从起始点到当前点的实际代价值；表示从当前点到目标点的估计代价值，称为启发函数。

A-star算法的应用关键在与启发函数和Open、Close列表的设置，好的启发函数可以加快搜索速度，合理的Open、Close列表设置能节省存储空间。Open列表用于存放未被检测过的位置点，Close列表用于存放已被检测完毕的位置点。

3 改进的搜索策略

首先， A-star算法的搜索核心是启发函数，启发函数使其避免了盲目性搜索的繁杂性。传统的A-star算法所使用的启发函数是经典的Manhattan距离或欧几里得距离。

分析A-star算法的搜索过程可知，当启发函数（是最终真实路径的距离）时，此时搜索范围较大，运行效率低下，搜索时间长；当启发函数时，算法的搜索过程将按照最理想的路径点一步步往下搜索，但是现在情况不能满足该种情况的要求；当时，搜索范围较小，运行效率较高，搜索时间较短，但是搜索出的路径不是最短的所以，为了得到较高的运行效率和最优的路径，我们应当选取启发函数的值接近于。因为A-star算法在进行下一步搜索时，只能搜索与其当前位置相临接的位置点，并不是任意、盲目地选取下一点。如图1所示，根据以上分析，本文结合Manhattan距离和欧式距离设置的启发函数如下式。

当时，代价函数改写为

当时，代价函数改写为

上式1.4中，和分别表示机器人当前节点与目标节点之间横坐标和纵坐标的差值，。

其次，在栅格环境中运用传统A-star算法进行路径搜索时，得出的结果会出现经过障碍物顶尖的情况，这在实际情况中是不允许的。分析算法在选取下一点的搜索原理可知，出现该情况的原因是在栅格环境中往左上、左下、右上、右下方向进行搜索时搜索的限制条件没有将与机器人当前位置相邻区域的环境情况考虑在内。本文对搜索过程做如下改进：

①机器人当前位置为，进行下一步的搜索，如果下一步位置为则执行②；如果下一步位置为则执行③；如果下一步位置为则执行④；如果下一步位置为则执行⑤；否则执行⑥；

②判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

③判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

④判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑤判断与机器人的相邻的、是否都为可行区域，若是则执行⑥，否则说明该路径是不安全的，需要重新搜索，执行⑦；

⑥计算此点的、、值。

⑦更新搜索节点。

4 实验仿真与结论

基于以上优化方法，本文在MATLAB2014b中进行了仿真，假设移动机器人的运动环境已知，为栅格化环境模型。图2为改进后的A-star算法仿真得出的路径规划结果，黑色为障碍物，白色为可行区域，其他颜色表示比较危险的可行区域。

与的传统A-star算法相比较，改进后的A-star算法搜索时间减少了0.04s，搜索的节点数减少了4.9%，路径的关键节点数减少了50%，并且路径没有过障碍物顶尖的现象，改进后的A-star算法会优先选择远离障碍物的安全区域规划路径，最终生成的路径更加符合机器人的运动控制。说明改进后的A-star算法是可行的。

机器人路径规划是一个经典研究领域，在当前复杂的生产、生活背景下，一方面对机器人的实时性提出了更高的要求，另一方面对规划出的路径安全性、与人相容性有了提出了更高的性能指标要求。本文充分考虑了机器人对实时性和安全性的要求，提出了改进的A-star路径规划方法，提高了搜索速度，降低了碰撞发生的可能性，并通过仿真实验验证了新方法的有效性。

参考文献

[1] 蔡自兴，贺汉根。未知环境中移动机器人导航控制理论与方法[M]。北京：科学出版社，2009.

[2] 王殿君。基于改进A*算法的室内移动机器人路径规划[J]。清华大学学报（自然科学版）。2012，Vol.52， No.8.

[3] 马喜峰， 张雷. 基于对称极多项式曲线的移动机器人平滑路径生成[J]. 机器人， 2005， 27（5）： 450-459.

[4] 翁敏，毋河海，杜清运，李林燕.基于道路网络知识的启发式层次路径寻找算法[J].武汉大学学报信息科学版.2006，31（4）：360-363.

[5] Roland S， Iiiah R N， Davide Scaramuzza， Introduction to Autonomous Mobile Robot[M]. USA： The MIT Press， 2012

路径规划典型算法篇3

（吉林工程技术师范学院信息工程学院，吉林 长春 130052）

【摘　要】本文通过对比求解最短路径问题的Dijkstra算法和Floyd算法的设计思想、求解过程和应用实例，讨论了两种算法的特点及适用领域。

关键词 最短路径问题；Dijkstra算法；Floyd算法

作者简介：高岚（1979—），女，吉林长春人，硕士，吉林工程技术师范学院信息工程学院，讲师，主要从事软件工程教学研究。

0　引言

最短路径问题是网络分析中最基本的组合优化问题之一，在公交路线网络规划中应用广泛。因此，实际公交线网优化设计中，路径选择算法成为一个重要研究课题，它直接关系到交通网络效率、传输延迟和吞吐量等主要技术性能指标。

早在20世纪初，最短路径这一重要问题就已得到人们的高度重视，当时有许多科学家研究这一问题的求解方法，但直到1959年荷兰计算机科学家Dijkstra（迪加斯特拉）才给出这一问题求解的基本思想，成为一代经典。当时的Dijkstra提出的这一算法主要解决的是从固定的一点到其他各点的最短路径问题。但实际生活中要求解的可能是任意两点间的最短距离，可采用Floyd（弗洛伊德）算法。本文通过将两种算法进行一些对比讨论，得出关于两种算法效率和适用问题的一些结论。

1　最短路径问题

最短路径问题是图论中的基本问题。在赋权图中，找出两点间总权和最小的路径就是最短路径问题。最短路径算法包括指定顶点对之间的最短路径算法和所有顶点间的最短路径算法，前者对于运输的合理化具有重要理论意义，而后者的意义在于选择合理的中转中心，使得总费用最少。在图论中最典型的两种求最短路径算法分别是Dijkstra算法和Floyd算法。

2　Dijkstra算法

2.1　算法基本思想

每次新扩展一个距离最短的点，更新与其相邻点间距离。当所有边的权都为正时，由于不会存在一个距离更短的没有扩展过的点，所以这个点的距离不会再被改变，因而保证了算法的正确性。根据这个原理，采用Dijkstra算法求解最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能破坏已经更新的点距离不会改变的性质。

2.2　Dijkstra算法思想在物流配送中的应用

采用图论中的最短路径算法Dijkstra算法来建立物流配送路径选择模型，主要思想是从代表两个顶点的距离开始，每次插入一个顶点比较任意两点之间的已知最短路径和插入顶点作为中间顶点时两点间的最短路径，得到的最终的权矩阵就反映了所有顶点间的最短距离信息。最短距离者作为费用最小者，即最佳的物流配送选址位置。

3　Floyd算法

3.1　算法基本思想

通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

3.2　Floyd算法在选址问题中的应用

某城市考虑建立区域内二次供水中转站。在选址问题中，点表示可供选址，其间连线表示运输费用，其需求点之间运费如图1所示。在选址中，要求该中转站到其他站点的距离最短，即运输费用最少，通过运用求解最短路径的Floyd算法可求出该网点布局的最佳中转站。

由计算可知，a到其他点的费用和为C(a)=33，同理C(b)=27，C(c)=18，C(d)=21，C(e)=33，比较可知c到其他各点的费用最小。因此本例从经济性考虑，选c点为中转站最优。

4　讨论

典型的最短路径求解算法Dijkstra算法和Floyd算法各有所长。Dijkstra算法可为任一源节点找出与其它所有节点的最短路径，是目前公认的较好的最短路径算法，但由于它遍历计算的节点很多，所以效率低。Floyd算法是一种用于寻找给定的加权图中顶点间最短路径的算法，是一种动态规划算法，可以算出任意两个节点之间的最短距离，代码编写简单，但是Floyd算法计算最短路径时时间复杂比较高，不适合计算大量数据。

综上，求解单源点无负权边最短路径可采用Dijkstra算法，而求所有点最短路径应用Floyd算法。对于稀疏图，采用n次Dijkstra算法比较出色，对于稠密图，适用Floyd算法。

5　结束语

本文通过对比两种求解最短路径算法的设计思想、求解过程、应用实例，讨论了算法的特点及适用领域。了解算法求解问题的差异，针对不同类型问题采取对应的求解算法，将大大提升解决问题的效率，对实际生产生活起到重要作用。

参考文献

［1］辛建亭,胡萍.图论在通讯网中的应用[J].2009,3.

［2］凡金伟,吕康.基于Dijkstra算法在物流配送中的应用[J].电脑编程技巧与维护,2009(4):39-45.

［3］邓春燕.两种最短路径算法的比较[J].电脑知识与技术,2008(12):511-512.

［4］徐凤生.求最短路径的新算法[J].计算机工程与科学,2006,2.

［5］殷剑宏,吴开亚.图论及其算法[M].合肥:中国科学技术大学出版社,2005.

［6］陈玉华.浅谈图论在现实生活中的应用[J].云南省教育学院学报,2004.

［7］王燕,蒋笑梅.配送中心全程规划[M].北京:机械工业出版社,2004.

［8］项荣武,刘艳杰,胡忠盛.图论中最短路径问题的解法[J].沈阳航空工业学院学报,2004.

路径规划典型算法篇4

关键词:水文计算;小流域;白塔堡河;无资料地区

中图分类号:TV122+.5 文献标识码:A 文章编号:1674-0432(2010)-06-0192-3

0 引言

在我国社会主义建设中,为了在小流域上修建农田灌溉排水措施、公路和铁路的桥涵建筑、城市和工矿地区的防洪工程,都必须进行设计洪水计算。因此,小流域设计洪水计算在工农业生产中有着重要的意义。小流域设计洪水的计算方法有很多,可以由流量资料推求设计洪水,也可以由暴雨资料推求设计洪水,但在小流域中很少设有水文观测站,往往缺乏实测的流量资料或暴雨洪水系列资料,因此常采用经验公式法、推理公式法、地区综合法、综合经验单位线法以及水文模型法等方法计算小流域的设计洪水。本文采用经验公式法和地区综合法计算白塔堡河的设计洪水,地区综合法就是采用相邻地区的实测及调查资料来确定各小流域的洪峰流量模数及其它统计参数,计算各小流域设计洪峰流量。

1 流域概况

白塔堡河位于浑河的左侧,是浑河的I级支流,该河发源于东陵区李相镇老塘峪村,流经李相、深井子、南塔、浑南新区、白塔、浑河民族开发区等六个乡镇(街区),于曹仲屯汇入浑河。流域面积182km2,河流总长48.45km,其中河流上游段为低山丘陵区,长29.4km,河道比降1.1‰。老塘峪至浑南新区教场桥之间为低山丘陵区,其下为平原区。该河中上游河道曲折,属宽浅式河床,中下游比较顺直,属窄深式河床。白塔堡河属季节性河流,平时无水或水量很小,汛期发生洪水时洪峰流量很大,极易造成洪水灾害。

2 计算步骤

白塔堡河没有水文观测站,其上游段的地貌特征与满堂河相似,满堂河上建有东陵水文站,本次水文计算采用东陵站21年降雨资料和《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》的理论分析方法,计算白塔堡河的设计洪水。

2.1 计算步骤

2.2.1 推求设计暴雨 根据实测暴雨资料,采用统计分析和典型放大法求得。

2.2.2 拟定产流方案 推求设计净雨,根据根据暴雨洪水资料,利用径流形成的基本原理,通过相关图法求得。

2.2.3 利用流域汇流方案 利用汇流的概念,用成因分析的方法求得。

2.3.4 推求设计洪水过程线 由求得的设计暴雨,利用产流方案推求设计净雨过程,再利用流域汇流方案由过程求得设计洪水过程设计净雨。

3 设计暴雨

3.1 典型过程及放大计算

利用东陵区的21年降雨量表,找出每年的最大1日、3日、7日降雨量并排序输入水文分析软件,其中21年最大七日降雨量见表1。并计算得出20年一遇的设计点暴雨,成果见表2。

通常寻找降雨量不均匀,并且又突然的强降雨作为典型年。根据表1,选择1996年作为典型年。

表1 21年最大七日降雨量

日期 1

(mm) 2

(mm) 3

(mm) 4

(mm) 5

(mm) 6

(mm) 7

(mm) 七天雨量

(mm)

1988 83.4 12.6 5.9 20.5 6.1 1.3 0 129.8

1989 16.6 2.7 11.5 11.1 8.9 47.2 0 98

1990 0 30.7 0.7 0 0 59.9 6.9 98.2

1991 16.7 13.3 1.4 0 26.4 35.2 8.5 101.5

1992 40.4 0.3 2.6 11.5 0 12 36.2 103

1993 10.7 8.2 62.3 48.4 54.3 6.2 42.4 232.5

1994 33 0 0 118.8 0 0 5 156.8

1995 17.8 67.5 38.1 0 73.7 41.5 6.9 245.5

1996 22.2 32.6 16 0.3 8.3 5.3 145.1 229.8

1997 2.8 0 0 0 135.5 5.8 0 144.1

1998 31.3 125.1 16.8 1.2 0.2 9.7 32.2 216.5

1999 0 0 0 76.2 9.8 0 0 86

2000 12 0 0 0 0 43 2.5 57.6

2001 92.8 14.4 9.5 11.8 0.5 47.8 0 176.8

2002 19.6 60.7 69.7 27.9 21.9 18.4 0 218.2

2003 2 2 1 0.5 152 0 0 157.5

2004 21.5 61 1.5 0 71.5 0 0 155.5

2005 17.5 24 5 0 32 94.5 0 172.5

2006 12.5 0.5 47 7 13.5 0 17 97.5

2007 114 6 0 0 0 0.5 0 120.5

2008 17 0 0.5 0 0 24.5 14.5 118.5

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中辽宁东部地区暴雨时-面-深关系曲线查得放大系数为0.99。则可得白塔堡河设计点暴雨量分别为

P1=142.6mm;P3=168.4mm;P7=238.9mm

根据已求出的设计暴雨量和选出的典型暴雨量计算放大倍比如下:

最大一天降雨量倍比

(1)

最大三天与最大一天雨量差额放大倍比

(2)

最大七天与最大三天雨量差额放大倍比

(3)

表2 p=5%设计暴雨

天数(天) 1 3 7

设计暴雨(mm) 144.09 170.2 241.41

3.2 设计暴雨时程分配

根据放大倍比,将1996年典型过程时段放大,便得出二十年一遇的设计暴雨时程分配,见表3

表3 设计暴雨时程分配

暴雨时空分布

天 1 2 3 4 5 6 7

典型年暴雨(mm) 22.2 32.6 16 0.3 8.3 5.3 145.1

Ki 0.98 0.98 0.98 0.98 1.9 1.9 0.99

P(mm) 21.96 32.28 15.88 0.294 15.77 10.07 142.69

3.3 设计洪水

3.3.1 降雨径流计算 根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中关于降雨径流的计算方法列出表4

表4 可能最大地面净雨时程分配计算

日次(天) 1 2 3 4 5 6 7

P(mm) 21.96 32.28 15.88 0.294 15.77 10.07 142.69

P-E(mm) 17.96 28.274 11.84 0 11.77 6.07 138.6333

RS(mm) 2 4.2 1.5 0 1.5 0.3 56

RS扣除(mm) 1.766 3.966 1.266 0 1.266 0.066 55.76

表4中P为设计暴雨时空分配,RS根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》附图辽宁省水文分区I23区降雨径流相关图查得,RS扣除为地面径流

3.3.2 可能最大洪水推求

(1)综合经验单位线的qm,tn值的确定

根据公式M=J0.25f0.5F=J0.25()0.5F=30.36

且D=0.24g=0.965

qm=DMg=6.47m3/s (4)

根据A=3b=0.556

(5)

tn=AGb=12天(6)

(2)瞬时单位线两参数n、k值的确定

以qm=6.47m3/s,tn=12天,he=10mm

(7)

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》附图查f(p)―P工作曲线P=1.4 计算出

n=P+1=2.4(8)

(9)

(3)求S(T)曲线并转化为Δt=24小时时段单位线计算表5

表5 用S(T)曲线转化时段单位线计算

t 0 1 2 3 4 5 6 7

t/K 0 0.116686 0.233372 0.350058 0.466744 0.583431 0.700117 0.816803

s(t) 0 0.002 0.009 0.0215 0.036 0.051 0.069 0.083

s(t-Δt) 0 0 0.002 0.009 0.0215 0.036 0.051 0.069

u(Δt,t) 0 0.002 0.007 0.0125 0.0145 0.015 0.018 0.014

q(Δt,t) 0 0.45 1.575 2.8125 3.2625 3.375 4.05 3.15

注:

(4)可能最大设计洪水过程推求最终列出设计洪水过程见图1。

图1 白塔堡河20年一遇设计洪水过程线

由图可知东陵最大洪峰流量为Q=258m3/s。

(5)白塔堡河最大设计洪水推求

根据《辽宁省中小河流(无资料地区)设计暴雨洪水计算方法》中公式由东陵站设计洪水推求白塔堡河设计洪水

Q白塔堡=Q山区+Q平原(10)

(11)

Q白塔堡平原=0.666(F白塔堡)0.824 (12)

根据公式(10)、(11)和(12)计算得白塔堡河设计洪峰流量为Q白塔堡=376.1m3/s。

4 结语

小流域很少设有水文观测站,往往缺少实测的流量资料或暴雨洪水资料。但各省都已编制完成水文手册,绘制出了暴雨等值线图,可以通过各省的水文手册来计算设计洪水。在小流域设计洪水计算方法上,地区综合法能根据相邻流域实测资料计算所规划的小流域设计洪峰流量,计算结果能够较合理的反应小流域设计洪水流量,满足小流域治理规划的要求。

参考文献

[1]叶守泽.水文水利计算[M].北京:中国水利水电出版社,2006.

[2]长江流域规划办公室.实用水文水利计算[M].北京:水文水利出版社,1982.

[3]辽宁省水文水资源勘测局.辽宁省中小河流(无资料地区)设计暴雨洪水计算方法[M].1998.

路径规划典型算法篇5

【摘要】本文通过分析了SPM模型，给出了传播模型CW测试的注意要点和数据处理方法。以某地市为例，介绍了利用CW测试对各种城区进行传播模型校正的情况及其结果。

 

【关键词】SPM模型；模型校正

1.引言

在移动通信系统运行过程中，由于终端位置不断发生变化，传播环境复杂多样，造成电波传播具有多样性和复杂性，因而建立在严格理论计算上的确定性模型很难实现。目前传播模型一般通过电磁理论推算和实测数据相结合的方式获得，即针对各个地市不同的地理环境进行测试，通过分析与计算等手段对传播模型的参数进行校正，以提高预测的准确性，从而获得符合本地市实际环境的无线传播模型。

 

在10年我公司进行3G网络规划时，为了得到准确的传播模型，我们在某地市挑选了几个典型的地点进行了传播模型的测试与校正工作，得到了包括城区商业区、住宅区，城郊等3种地形下的传播模型参数，利用得到的模型，我们进行了网络的仿真，以帮助我们进行3G无线网络的规划工作，本文正是基于该次的传播模型校正的情况进行论述。

 

2.3G无线传播模型

传播模型表征的是在某种特定环境或传播路径下电波的传播损耗情况。其主要研究对象是传播路径上障碍物阴影效应带来的慢衰落影响。在传播模型研究方面主要有如下两种流派：直接应用电磁理论计算的确定性模型，基于大量测量数据的统计模型，又称为经验模型[1]。

 

在3G系统的2.1G核心频段上，通常使用的经典模型有Cost231、射线跟踪等。从精确程度看，射线跟踪是最接近实际情况的，但由于它对数字地图的高精度要求，无法大规模普及，本文选用的是标准传播模型（SPM）。

 

2.1 理论分析方法的研究

射线跟踪模型基于3D数字地图，充分考虑建筑物的特征和分布对信号传播的影响，通过理论计算得出每一点上的接收信号强度。因此，根据射线跟踪模型的预测结果，可以精确地进行网络规划并有效地控制干扰。建立步骤如下：

 

首先确定一个发射源的位置，根据3D地图上建筑物特征和分布，找出发射源到每个接收位置光线的所有传播的路径，并根据各种的无线传播理论公式进行计算，得到每个测试点的接收场强，由于该模型要求的数字地图很高，需要带详细建筑信息的三维数字地图，对于算法要求非常严格，一般甚少使用。

 

2.2 实测统计方法

实测统计的方法就是基于一个经验的传播模型，通过试验测试的方法，并利用计算机规划软件进行辅助计算，修正模型的各个参数，得到不同地形下的模型参数，其中，这里的试验测试，主要是指CW（连续波）测试。而传播模型最常用的是标准宏小区（Standard MacroCell Model）传播模型。

 

其中：Ploss传播路径损耗（dB）；d是基站到移动站之间的距离（km）；Hms是移动站天线有效高度（m）；Heff是基站天线的有效高度（m）；Diffn是使用Epstein Peterson、Deygout或Bullington的等效刃形衍射方法计算的衍射损耗；k1 & k2：截距和斜率；K3：移动天线的高度因数；K4：Hms的Okumura Hata的Multiplying Factor；K5：有效天线高度增益；K6：Log（Heff）Log（d）。这是log（Heff）log（d）值的Okumura Hata类型的Multiplying Factor；K7：衍射系数；Clutter_Loss：地物损耗参数。

 

3.传播模型校正流程

一般取用CW测试来进行模型的校正，CW测试是通过连续波，采用全向天线发射信号，接收机在服务区内各个方向的道路上进行测试，以得到不同方向、距离的场强值，CW测试模型校正工作流程如图1所示。

 

（1）测试工具

测试工具主要是用来发射和采集模型校正所需要的原始数据，包括信号发射部分和接收部分，信号发射部分一般放置在位置相对较高的地方及放置在测试区域的中心地点，其中本次测试的发射单元选取了上海诺恩科技公司的WHT2005测试发射机，接收单元NORN LiteScan扫频仪2005，其他还有电脑，GPS，接收机，车载电源，hub，逆变器，车载电源一拖二，前台测试软件，加密狗等必要工具。

 

（2）测试基站/路线制定

根据地形地貌特征选择典型地点作为测试基站，安装发射设备，根据站点周围的地理环境制定测试路线，对于测试基站设置的个数，一般在人口稠密的城市，测试站址应不少于5个，中等规模的城市选取2-3个，中小城市及郊区1个就够了。对于测试路线，为了足够的采样数据，在市区一般测试要求达到10公里左右的距离，在郊区一般在15Km到20Km。由于无线电波在离发射天线很近的地方无法用公式模拟，只是用一固定衰减值，所以在测试中离发射天线很近的地方（一般是0.5Km-1Km）不需要做大量测试。本次某地市传播模型的校正共进行了三个地点的测试，主要如下（见表1）。

 

（3）无线测试

根据所选择的测试站点和测试路线进行原始数据的采集。

（4）测试数据的后处理

测试结束后对测试数据进行整理，该项工作是传播模型校正的核心，一般都是依靠计算机的规划软件进行数据的处理，本次是使用了软件是百林规划软件[2]。

（5）传播模型参数修正

通过百林软件平台，利用Standard MacroCell Model模型[3]进行了模型优化，给出适合某地市各种地形环境下的无线传播模型。

（6）报告输出

对整个工作内容提交报告。

4.参数校正

4.1 K2校正

K2是与频率相关的因子，在校正的过程中一般采用先校正K2再反过来对K1进行校正。

4.2 K1的校正

K2校好后可，则此时图中的intercept即为K1的偏差（实际应为[K1+K3（Hms）+K4log（Hms）+K5log（Heff）+K7diffn]的偏差，但可先假设K3（Hms）+K4log（Hms）+K5log（Heff）+K7diffn]为常数，则此就为K1的偏差），将原K1值加上intercept即得K1的校正值。也可以用Analyse功能得到此偏差值

 

4.3 K3、K4的校正

K3、K4与移动台天线高度相关的因子，该值对传播模型的影响一般不大，可以取缺省值，一般可取-2.93和0.00。K3、K4的变化可由K1来弥补，因此一般取了缺省值后，就可以无需调整。

 

4.4 K5、K6的校正

路径规划典型算法篇6

[关键词] 动态规则 方法 配送线路

配送中心货物配送的线路直接影响到配送的效率、成本，进而影响到顾客的满意度，因此，如何使配送线路最优即路程最短，一直是理论及企业关心的问题。以前解决此问题的方法主要是应用图论的方法，但该方法的缺点是，当线路复杂时计算较为烦琐，而应用动态规划的方法能有效解决这个问题。

一、模型建立

设n个顶点，每两个项点之间有边连接，现要求从某一个结点出发，经过每一个结点一次且仅一次，最后回到出发时结点，要求路径最短，这就是最优哈密顿回路问题。这个问题用图论语言叙述为：考虑n个顶点无向完全图，为顶点集合，E为边集合，为两结点之间距离。

采用动态规划法计算。考虑顶点1为始点（为了书写方便，把顶点等简化为123）和终点的一条周游路线。每条这样的路线均可表示为形式:对于某个路线包含了一条边和顶点k到1的一条通路，这条通路必须经过V－{1,k}的每个顶点各一次。不难看出，如果以顶点1为始点和终点的某条周游路线是最佳的，那么，这条路径上从顶点k到顶点1的部分路径（经过V－{1－k}的每个顶点各一次），必须是从k到1的一条最短路径。因此，最佳原理是适用的。设(i,S)是从顶点i出发，经过S中除去顶点1之外的其它顶点各一次并回到顶点1的一条最短路径的长。于是g(1,V－{1})就是一条最佳旅游路线的长。根据最佳原理，我们有

一般地，当时，有

.

如果对所有选定的k，已知，则可以求得。各的值可逐步求得。令，这是初始状态。往后，依次对元素个数为1的集合S，求得所有的。然后求和绝对值S=2的所有的等等。当时，对任何必须满足。最后可求得问题的最佳解，我们称这种方法为图论中的动态规划方法。

二、算法实例

集中存储统一配送是现代化连锁经营的典型物流模式。以一个配送中心为10家门店进行配送服务的业务流程为例进行线路优化设计，连锁经营集团在门店不设有仓储设施，由各供应商集货到配送中心，由配送中心统一配货和保管。配送中心以技术为支撑，它是各门店供货枢纽，配送中心建立了有效的信息处理系统如 POS 系统通过运输车队按照各门店的需求进行配送，门店由于没有设置仓储设施增加了营业面积，降低了各门店仓储人力资源成本。对各门店配送路线的优化选择是典型的最短路径求解方法。由 POS 系统把各门店的全部需求信息后反馈给配送中心， 由配送中心根据商品需求信息制定配送计划并对配送路线做出最佳选择，对各门店进行多品种、小批次、多频率的配送，路线优化设计从配送中心开始，车辆经过 10 家门店且只经过一次，最终完成配送任务返回配送中心使总路程最短。

配送中心采取共同配送方式为各门店配货，共同配送是为了提高物流效率，通过配送中心集中运输货物的一种方式。可以把多种货类集货于一辆车，既提高了车辆的满载率又提高了配送效率。减少了运输自身行为带来的外部不经济如破环生态环境、噪声污染、交通拥挤，即有利于企业经济利润最大化又使整个社会经济的可持续发展。

某配送中心与各连锁店之间的距离用矩阵表示，矩阵中的元素aij表示第i个超市与第 j 个超市之间的距离：

约束条件：为各门店实行配送服务的车辆从配送中心出发最终回到配送中心，各门店的配送业务由一辆货车完成；每个门店都必须有货物需求量，所有门店的货物需求量总和不超过配送车辆的载重量。

要研究的问题是一辆非满载车辆从配送中心出发经过各个门店配货仅一次并且返回配送中心，约束条件是每个配送任务都需要完成而且货物不能超载，要求配送运输路径最短，这是一个最短的哈密顿回路问题。为了找到由0至10的最短线路，可以将该问题成为0―1―2…10 11 个阶段，在每个阶段都需要作出决策，即在0点需决策下一步到哪个门店;同样，若到达第二阶段某个状态，比如1，需决定走向1还是2;依次类推，可以看到：各个阶段的决策不同，由0至10的线路就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离而且直接影响后面阶段的配送线路。所以这类问题要求在各个阶段选择一个恰当的决策，使由这些决策序列所决定的一条路线对应的配送线路最短。

下面用无向图来表示各门店之间的连通情况。说明如下：节点j表示第j个门店，连接两个门店的边上注明的数字表示两个门店之间的距离。显然这个图是有11个节点的完全加权图，此图共有边条边，为了清楚起见我们不画出所有的边。

按照前面图论动态规划方法，找出最短路径的配送方案为：0132546789100

采用动态规划方法计算量比较小，因而节省时间。例如结点系数为n时，一般情况下找出最短哈密顿回路第一个结点到第二个结点n-1种走法，第二个结点到第三个结点有n-2种走法……，共有1/2（n-1）!，不同哈密顿回路为了比较权大小，对每条回路要做n-1次加法，当n较大时，浪费时间是很多的，如果按动态规划算法，设N是未计算g(1，-{1})前需要计算g(i，s)的个数，对于每一个{S}，i有n-1种取法，又包括1和i取大小为k的不同集合个数是，因此，显然计算量要比较其他算法要小的多。

参考文献:

[1]胡运权:运筹学基础及应用[M].哈尔滨工业大学出版社，1998年2月版

[2]李军郭耀煌:物流配送车辆优化调度理论与方法[M]. 中国物资出版社，2001年3月版

[3]毛薇:物流园区规划及运营关键技术研究[D].天津大学.2005年

路径规划典型算法篇7

关键词： B样条曲线； 无人车； 路径规划； 碰撞检测； 最大曲率约束； 最优路径

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0235-03

B-spline Curve based Trajectory Planning for Autonomous Vehicles

QU Pan-rang，LI Lin ， REN Xiao-kun ，JING Li-xiong

（Institute of Aeronautics Computing Technique Research， Xi’an 710065， China）

Abstract：Path planning is an important research topic in the field of the unmanned vehicle motion planning， and it directly affects the performance of unmanned vehicles in a complex traffic environment. Taking the requirement for smoothness into account， this paper proposed a method based on B-spline curve and built a planning model which can be divided into four steps， including path clusters， constraint of maximal curvature， collision detection and optimal path. This method works efficiently and simulation results show efficiency of the method.

Key words：B-spline curve； autonomous vehicle； path planning； collide detection； constraint of maximal curvature

1 引言

近年来，无人驾驶技术备受关注，各大研究机构和企业争相推出各自的无人驾驶平台。无人车作为未来智能交通的主要主体也逐渐融入到我们的日常生活中，比如自主巡航[1]和自动泊车等等。然而，为了使其更好地服务于我们，需要进一步提高其智能化水平，而路径规划作为连接环境感知和运动规划的桥梁，是无人车智能化水平的重要体现[2]。

由于受到自身动力学和运动学模型的约束，车辆的路径规划问题除过要严格满足端点状态约束之外，还要求其中间状态满足运动系统的微分约束。由于实现简单，并且高阶多项式曲线能够很好地满足运动系统的微分约束，生成高阶平滑的路径，所以很多路径规划系统选择使用基于多项式曲线的方法生成路径。B样条曲线是一种典型的多项式曲线，且因为其所有的中间状态均是由控制点加权生成，所以其能够完全满足端点状态约束。综合考虑无人车路径规划的要求和实现复杂度，在仅已知初始位姿和目标位姿的情况下，本文选择B样条曲线生成路径，重点讲述分步规划模型，即路径簇生成、最大曲率约束、碰撞检测以及最优评价四个过程，并通过Matlab仿真对本文方法进行了验证。

2 问题描述

本节分别描述了无人车路径规划问题和B样条曲线。

2.1 路径规划问题描述

路径规划得到的是一条从初始位置到目标位置的路径，即二维平面内一条从初始位置点到目标位置点的曲线，曲线上的每一个点表示车在行驶过程中的一个状态。考虑到实现方便，本文将路径描述成离散点序列[Sstart，S1，???，Sn，Sgoal]，如图1所示，序列中每一个点[Si（xi，yi，θi）]表示车的一个状态，其中[（xi，yi）]表示此时刻车辆的位置，[θi]表示车辆的航向，[Sstart]和[Sgoal]分别表示车辆的初始状态和目标状态。图1中的圆[（xobs1，yobs1，robs1）]表示环境中的障碍物，[（xobs1，yobs1）]表示障碍物的位置信息，[robs1]表示障碍物的半径。

2.2 B样条曲线

如果给定[m+n+1]个控制点[Pi（i=0，1，???，m+n）]，就可以构造[m+1]段[n]次B样条曲线，其可以表示为公式1：

[Pi，n（t）=k=0nPi+k?Fk，n（t） ，t∈[0，1]Fk，n（t）=1n！j=0n-k（-1）j?Cjn+1?（t+n-k-j）n ， t∈[0，1] ， k∈0，1，???，n] （1）

其中，[Pi，n（t）]表示第[i]个[n]次B样条曲线片段，[n]表示B样条曲线的次数，[t]为控制参数，其取值范围为[[0，1]]，[Pi+k]为控制点，[Fk，n（t）]为B样条基。依次连接全部[n]阶B样条曲线段就组成了整条B样条曲线。

3 本文算法

本节重点讲述基于B样条曲线的路径规划方法和基于该方法生成路径的过程。

3.1 基于B样条曲线的路径规划方法

选择三阶B样条曲线生成几何路径，即每四个控制点生成一个路径片段，然后通过片段的拼接就可以实现从初始状态到目标状态的路径规划，下面着重讲述基于六控制点的三阶B样条曲线生成满足车辆端点位姿约束路径的方法，如图2所示。

l 依据初始状态选择控制点[P0，P1，P2]。当[P0，P1，P2]三个控制点共线，并且[P1]为线段[P0P2]的中点时，生成的B样条曲线与线段[P0P2]相切于点[P1]。所以选择无人车的初始位置为控制点[P1]，将控制点[P0]和[P2]选在初始航向角[θstart]所在直线上，并关于控制点[P1]对称。如是，即能满足车辆的初始位姿约束；

l 依据目标状态选择控制点[P3，P4，P5]。当[P3，P4，P5]三个控制点共线，并且[P4]为线段[P3P5]的中点时，生成的B样条曲线与线段[P3P5]相切与点[P4]。所以选择无人车的目标位置为控制点[P3]，将控制点[P3]和[P5]选在目标航向角[θgoal]所在的直线上，并关于控制点[P3]对称。如是，即能满足车辆的目标位姿约束。

（a） 路径簇

（b） 最大曲率约束

（c） 碰撞检测

3.2 分步路径规划

本小节将以图3所给定的场景为例，讲述最优路径生成的过程。

3.2.1 路径簇生成

在选定控制点[P1]和[P4]之后，通过选择不同的控制点[P2]和[P3]，从而得到多组控制点，进而得到多条路径。将控制点选择的极限定为线段[P1P2]、[P3P4]与[P1P4]相等，但是[P1P2]和[P3P4]不能出现交叉。将这个范围等间隔量化，各取四个点，共组成16组控制点，得到16条路径，如图3（a）中的蓝色曲线所示。

3.2.3 最大曲率约束

理论上，车辆的最小转弯半径[Rmin=Lsin（θmax）]是其本身属性[3]，只取决于车辆的轴距[L]和最大前轮转角[θmax]。那么，车辆可行驶路径的最大曲率[κmax=1Rmin]也是固定的，假设无人车可行驶路径的最大曲率[κmax=16]，以此为约束条件，在路径簇中选择满足最大曲率约束的路径，如图3（b）所示，图中绿色曲线表示不满足最大曲率约束的路径。

3.2.4 碰撞检测

碰撞检测的目的是保证车辆在规划路径上行驶而不与障碍物发生碰撞。采取的碰撞检测的方法很简单，因为环境中的障碍物采用圆来描述，所以只要判断路径上每一点到圆心的距离与障碍物半径的关系，就能确定其是否发生碰撞。由两点间距离公式：

[d=（x1-x2）2+（y1-y2）2] （2）

如果[d]大于障碍物半径，则不发生碰撞；如果[d]小于障碍物半径，则发生碰撞。图3（c）中的蓝色曲线表示既满足最大曲率约束，又不与障碍物碰撞的路径。

3.2.2 最优路径

路径要求的侧重点不同，优化的目标函数也可以有多种选择，常用的目标函数有最短和最平滑等。其中，路径最短可以抽象成优化问题：

[traoptimal=arg mintraids] （3）

路径最平滑可以抽象成优化问题：

[traoptimal=arg mintraiκ2] （4）

式中，[traoptimal]为最优路径，[traids]为第[i]条路径的长度，[traiκ2]为第[i]条路径上所有点处的曲率平方之和。图3（d）中的红色曲线即为得到的最短可行驶路径。

如是，就能得到满足车辆运动学约束，并且无碰撞的最优路径。

4 结论

本文选择使用B样条曲线解决无人车路径规划问题，并建立了基于B样条曲线的分步规划模型。仿真结果表明，使用基于B样条曲线的路径规划方法能够很好地解决简单障碍物场景中无人车的路径规划问题，并且因为路径生成过程简单，所以该方法常常表现得十分高效，能够完全满足无人车路径规划系统对算法实时性的要求。

参考文献：

[1] Vahidi A， Eskandarian A. Research advances in intelligent collision avoidance and adaptive cruise control [J]. IEEE Transactions on Intelligent Transportation Systems， 2003， 4（3）：143-153.

[2] Siegwart R， Nourbakhsh I R， Scaramuzza D. Introduction to autonomous mobile robots [M]. US： MIT press， 2011.

路径规划典型算法篇8

【关键词】 传播模型 Okumura模型 HATA模型 SPM模型 模型校正

一、概述

宏蜂窝传播模型在无线网络规划中是非常重要的，它是移动通信网宏蜂窝小区规划的基础。我国幅员辽阔，各省、市的无线传播环境千差万别。因此，一个良好的移动无线传播模型很难形成。为完善模型，需要利用统计方法，测量出大量数据，对模型进行校正。

二、宏蜂窝传播模型的分类

宏蜂窝传播模型在建立时，使用地形数据来确定无线电波传播路径，无线电波传播路径就是发射机和接收机之间的地形轮廓。

1 、Okumura模型

Okumura模型是预测城区使用最广泛的模型。它以准平坦地形大城市市区的中值场强或路径损耗为参考，对其他传播环境和地形条件等因素分别以校正因子的形式进行修正。它的应用频率为150-1920MHz（可扩展到3000MHz）；发射天线有效高度为30-200m；接收天线有效高度为1-10m，有效距离为1km-20km。

2、HATA模型

HATA模型适用于小区半径大于1km系统的路径损耗预测，根据应用频率不同，HATA模型分为：Okumura-Hata模型和COST-231 Hata模型。

Okumura-Hata模型频率范围是150-1500MHz，基站天线有效高度为30-200m，移动台天线高度为1-10m。该模型以市区传播损耗为标准，其他地区在此基础上进行修正。

Okumura-Hata模型作了3点限制：

适用于计算两个全向天线之间的传播损耗；

适用于准平滑地形而不是不规则地形；

以城市市区的传播损耗为标准，其他地区采用修正因子进行修正。

对于较高的频段，在Okumura-Hata模型基础上进行了扩展，形成了COST-231 Hata模型。COST-231 Hata模型的使用条件是：频率为1500-2000MHz；基站天线有效高度为30-200m；移动台天线高度为1-10m；通信距离为1-35km。

3、SPM模型

SPM模型是建立在COST-231 Hata模型的基础上，现已广泛应用到3/4G移动通信设计的领域中。常用的SPM模型中的标准宏蜂窝小区模型应用较广，其计算公式如下：

式中D为收发台之间的距离；HTeff为发射天线的等效高度；DiffractionLoss为路径上有障碍物而引起的衍射损耗；HReff为移动台的等效天线高度；Kclutter为常量因子；F（clutter） 为地形平均损耗。K1与K2为截距和斜率。

三、传播模型的校正

模型校正分3个步骤。准备数据、数据处理和模型校正

1、数据准备

主要对电子地图与基站数据、区域划分、测试站址的选择、CW波测试过程和数据采集等五部分内容进行准备。

2、数据处理

数据处理最主要的目的是滤除测试中带入的不合理数据，然后转换成模型调校所需要的文件格式。主要通过对现网路测数据后处理，测试数据GPS调整后，再进行计算。计算主要是测试数据计算导频的瞬时接收总功率和bin的导频接收功率均值。

得到了bin的导频接收功率均值以后，就可以计算该点的路径损耗。

3、模型校正

模型校正是整个校正工作的最后一步，需要借助专用的网络规划软件来完成。下面以通用模型来举例。通用模型的公式是：

Pr= Pt + K1 + K2lgd + K3lghb + K4+ K5lghblgd + K6hm + K7

利用该模型的校正方法是：首先选定一个模型并设置各参数值K1 - K7值，然后以该模型进行无线传播预测，并将预测值与CW值做比较，得到一个差值，再根据所得的差值统计结果反过来修改模型参数，经过不断地迭代处理，直到预测值与CW值的均方差以及标准差最小，得到的模型参数值就是所需要的校正值。

四、结论

通过本文介绍，对宏蜂窝的传播模型以及模型校正方法有了初步了解，根据不同频率和不同场景特点选定合适的模型，以及根据当地的地理特点对模型进行校正，对规划的准确性、合理性将有较大的帮助。

参 考 文 献

[1]杨大成等 《移动传播环境理论基础.分析方法和建模技术》 机械工业出版社2003年8月第1版第1次印刷