第六章智能车辆导航系统

车载GPS定位技术与应用

§1、智能车辆的分类§2、路径规划§3、自主式车辆导航系统的设计§4、中心决定式车辆导航系统的设计第五章 智能车辆导航系统6.1智能车辆导航系统的分类智能车辆导航系统是集成了自动车辆定位系统技术、地理信息系统技术、数据库技术、多媒体和现代通信技术等的高科技综合系统。从实现导航功能的角度看，目前可分为两大类：自主式（分布式）车辆导航系统，其定位和路径规划等功能全部在车载设备实现。中心决定式导航系统，它的某些功能需要借助通信网络才能实现。6.2路径规划解决的是：在给定的数字道路地图中寻找从出发地到目的地的最优路线。针对实际应用，可以采用不同的优化标准，如最短行车距离、最少旅行时间、最低通行收费等。计算道路网络中两点之间的最优路线问题都可以归结为求解带权有向图的最短路问题。最短路问题最短路径：就是指在带权有向图中，寻找从指定起点到终点的一条具有最小权值总和的路径。6.2.1经典的最短路算法1、迪杰斯特拉(Dijkstra)算法：由荷兰数学家E.W.Dijkstra于1959年提出的一个适用于非负权值网络的单源最短路算法，是目前求解最短路问题的理论上最完备、应用最广的经典算法，它可以给出从某指定节点到图中所有其他节点的最短路。迪杰斯特拉(Dijkstra)算法主要思想是：按照路径长度逐点增长的方法构造一棵路径树，从而得到从该树的根节点(即指定起点)到其它所有节点的最短路。具体做法是：设集合S存放已经求出的最短路径的终点，初始状态时，集合S中只有一个源点V0。以后每求得一条最短路径(V0，…，Vk)，就将Vk加入到集合S中，直到全部顶点都加入S中为止。51643208562301371732913长度最短路径<V0,V1><V0,V2><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>813192120按路径长度递增次序产生最短路径算法：1、把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合2、将T中顶点按最短路径递增的次序加入到S中，

保证：（1）从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度3、依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和。求最短路径步骤1、初始时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在<V0,Vi>，为<V0,Vi>弧上的权值若不存在<V0,Vi>，为2、从T中选取一个其距离值为最小的顶点W，加入S3、对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值4、重复上述步骤，直到S中包含所有顶点，即S=V为止终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0,V2,V3,V4>--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>516432085623013717329--------------------------------21<V0,V2,V3,V4,V5>--------21<V0,V2,V3,V4,V5>每一对顶点之间的最短路径方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次方法二：弗洛伊德(Floyd)算法2、弗洛伊德(Floyd)算法算法思想：逐个顶点试探法求最短路径步骤初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值所有顶点试探完毕，算法结束例ACB264311041160230初始：路径：ABACBABCCA046602370加入B：路径：ABABCBABCCACAB0411602370加入A：路径：ABACBABCCACAB046502370加入C：路径：ABABCBCABCCACAB6.2.2算法的时间复杂度估计（1）一个算法的时间复杂度，就是执行该算法的计算工作量，即算法的时间代价。为了能够比较客观的评价一个算法的效率，在度量一个算法的工作量时，应该与具体的计算机软硬件因素无关，而只依赖于问题的规模n。1892年PBachmann发明了一种表示函数渐进特征的方法，称为大O表示法，它的定义为:当且仅当存在正整数c和n0，使得T(n)<cf(n)对所有的n≥n0成立，则称该算法的渐进时间复杂度为T(n)=O(f(n))，简称时间复杂度，它表示当问题规模n充分大时，算法的时间复杂度随n变化。在使用大O表示法时，需要考虑关键操作的程序步数，在大多数场合里，程序步数与执行频度是一一对应的，如果最后给出的是渐进值，可以直接考虑关键操作的执行频度，找出其与n的函数关系，从而得到渐进时间复杂度。常见的算法时间复杂度有：常量阶，表示运行时间与问题规模无关或不超过某一常数;线性阶，表示运行时间与问题规模呈线性关系，类似的还有平方阶、对数阶、指数阶等。（2）优化运行数据结构经典Dijkstra算法的核心代码用C语言实现如下:算法的时间复杂度为要降低算法的时间复杂度，关键在于对子循环②加以改进，该子循环的目的是从不断变化的V-S集合中，找出下一条最短路径并返回其父节点指针和累计权值，如果采用各个节点在算法中距离源点的最短路径长度来构造优先级队列，将具有较高优先级的节点放在队列的头部，则能有效提高选择V-S集合中最短路径顶点的效率。引入堆结构作为优先级队列的存储表示，能大大提高运算效率，k叉堆是一种最普及的堆结构，它把一个关键码集合K=[k0,k1,…，kn-1:}中的所有元素按完全k叉树的顺序存储在一个一维数组中，显然该完全k叉树的高度为[logk(n+k-1)]-1，如图6-1是一个四叉堆优先级队列及其对应的完全四叉树。堆结誉构中看除了罚根节鹊点外授的所倚有其依它节泰点i的关巡寿键码k[饿i]必须瞎满足:k[瓶i]欠≤k[壮pa超re妙nt剂(i)]宅(或者k[辱i]贵≥约k除[pa止re剑nt陈(i)]鼓),i伐=铜1,喂2,准…,贯n剪-1即某业个节成点的非值不圣小于(不大始于)其父牌节点醋的值桨，这纠样堆田中最挽小(最大)元素挺的值尼就存伤放在呜根节修点中尿。图6.盲1四叉寇堆及欢对应灶的完裕全四园叉树在Di坑jk涌st类ra算法竭中需瓦要用狱到堆肃结构底的四陷种操笼作:(1酒)he飞ap摧es让crea咸te扔(h):创建盟堆h，其沾时间勉复杂卵度为O(允1)怪;(2宗)梯he缠ap还-i乳nse享rt谨(h馒,x):在堆h中插鸭入一脑个新量数据斑项x，其趣时间畏复杂蹲度为(lo务gn)丈;(3蚁)说he解ap一de晶le乒temi节n(个h,讯x):从堆h中找扫到具粥有最吉小属赢性值柔的数招据项滨，将移其删浊除并格作为烤操作投结果拍返回语，挠其时挡间复零杂度接为O(线lo堵gn)杯;(4仍)he尤ap摸se锁decr摊ea灰se一ke弃y(辜h,凡x,断va义lu谊e):将堆h中的秤数据刺项x的属会性值全用一档个更鹅小的偏数va脂lu谈e代替淘，脑其课时铅间早复必杂度霸为O(略lo旷gn)。k叉堆毙结构血操作浊的时睁间复朵杂度6.倘2.敏3启发织式搜地索算覆法启发颂式搜标索是枣基于灰知识脊的搜施索策笨略，腿即通螺过选电定一殊种估打价函校数，在搜元索过践程中膝的每遣一步扔，寻神找估密价函侍数数靠值最笼高的材节点丈作为贫下一苍个搜尖索节茶点。基于阁启发缸式搜书索的诸最短轻路算挖法有Co停st括ed算法毁、分浸支界照定法粪、限械制搜愧索区止域法膛、A*算法俘等，纽奉利用镇启发虎式信胃息的祸有效族方法贝是计绒算启雹发式膜函数传，该函数航估价稿每一邻生成区节点脊处于卧最佳您路径小解上映的可闯能性抱，从淘而优浪先搜俱索可字能性茶大的尺节点，达态到提烂高搜鞋索效旗率的贝目的秀。6.穴2.驱3.杏1田A*算法该算堂法在长选择矩下一恶个被纠检查雪的节兆点时优，对当练前节骡点距醒离终队点的帖长度愈作为雨估计蓬，评片价其轻处于谊最优墨路线饼上的罢可能寻性量破度，这样阀就可谋以首毯先搜然索可译能性肢较大题的节溪点，好从而悉提高值搜索姜过程身的效输率，底如下砖图所示标。6.梯2.亭3.漠1醒A*算法原理后简介A*（A-阔St基ar铁)算法是一件种静浙态路遍网中亡求解忍最短名路有眠效的型方法鸦。公式螺表示尽为：f(求n)=g(扫n)艘+h匆(n),其中f(制n)是从其初始先点经艳由节摩点n到目坚标点面的估诉价函如数，g(艺n)是在自状态舰空间款中从缎初始臣节点净到n节点攻的实株际代亭价，h(朋n)是从n到目乘标节充点最吃佳路堂径的赛估计顷代价钳。保证赌找到最短比路径（最辜优解浙的）葛条件对，关仓键在笔于估阔价函晶数h(滋n)的选呆取：估价类值h(伴n)<壳=挑n到目监标节乌点的找距离稿实际垄值，弄这种俭情况讯下，板搜索筝的点掩数多配，搜限索范径围大狮，效温率低东。但泰能得斯到最剧优解烟。如果虹估茄价值>实际毫值,搜索次的点剃数少决，搜界索范金围小盗，效兵率高捏，但侵不能笋保证求得到扶最优庭解。1)如果莲选择么最短析距离幼为优剩化标常准，那么以顶稿点累梳计权土值d(款v)作为许当前禁顶点趋的实喝际费预用，傻以当依前顶才点到纹终点抱的欧帮式距匀离d'警(v)作为抗最小啊费用挺估计捷函数煮，那么局顶点v的启陈发式逗估价参函数北为:f=g(故n)狸+s沃qr醉t(救(d裙x-肃nx)*朽(dx曲-n畏x)色+(略dy站-n棕y)*隙(dy票-n滴y))；这样醉估价鲜函数f在g值一是定的隶情况遵下，肯会或功多或面少的使受估忙价值h的制僚约，拣节点江距目贡标点茎近，h值小广，f值相杨对就枝小，济能保斗证最士短路临的搜捷索向猜终点轧的方岸向进诊行。庸明显名优于Di活jk睁st重ra算法的毫挪无无东方向叛的向解四周叔搜索饺。估价振值与配实际龄值越滋接近接，估蝴价函切数取徒得就撕越好如果糠选择统最少金出行波时间玻为优境化目爽标，则可孕定义愧顶点v的启互发式仍估价劝函数珠为其中t'盏(v)为出养行时格间，d(拢v)为从凳起点畏到当太前顶丧点的符最短讨路径缓，di(v)为路德段i的长炎度，Vi(v)为路谎段i的行稠驶速舌度，V'除(v)为估临计的晋最大槐行驶订速度主要焦搜索婆过程班伪代增码如件下：创建免两个能表，OP宇EN表保征存所建有已校生成阁而未但考察仓的节声点，CL卵OS漆ED表中长记录撒已访滩问过斥的节蛇点。算起两点的虹估价代值;将起环点放棍入OP音EN表;wh括il带e(示OP悬EN!=因NU锻LL师){从OP锡EN表中淋取估程价值f最小劫的节开点n;if燃(n节点==目标肠节点){br待ea停k;}fo心r(当前染节点n的每荣个子悠节点X){算X的估牧价值;if阿(Xin某O报PE跌N){if(芹X的估叔价值塌小于OP拿EN表的恒估价锦值){把n设置纤为X的父寒亲;更新OP上EN表中爆的估踪蝶价值;胖//取最薯小路屿径的佩估价旷值}}if钻(Xin等CL答OS叛E)缸{co怨nt绸in妇ue示;}if急(Xno影tin顾bo辽th){把n设置柴为X的父硬亲;求X的估映价值;并将X插入OP杰EN表中;细//还没遮有排甲序}}/吓/e原nd恋f也or将n节点拌插入CL词OS测E表中;按照平估价装值将OP翁EN表中款的节点排序;//实际紧上是珠比较OP谦EN表内容节点f的大控小，摊从最者小路乐径的暮节点兄向下弦进行缠。}/洽/e阴ndwh凉il蜓e(勺OP学EN!=体NU统LL朱)保存蒜路径阶，即播从终鸽点开村始，涝每个厨节点秋沿着延父节耀点移庭动直笑至起颂点，州这就脉是要述求的快路径飞；6.陕2.完4双向隔搜索贴算法双向俭搜索语是指弱：除饱了像孩普通刚单向请搜索竖那样粪从起彼点出社发向结终点融搜索争最优性路线抢外，蜂同时华还由册终点羞出发趋向起辛点进乔行反健向搜史索。计算贞某一匀顶点别对之积间的只最短汉路径摊，算字法包洋括两贪个部蔽分:第一劝部分孕选择堡一条运用于零扩展砍的路砌径，扩并扩勇展该歌路径寒；第二晕部分苗检查今是否凉己经朗找到连最短即路径随。这两惠步循皇环进盲行，刊直到琴第二龙步中冻的条泥件满压足，坚最短躬路径识找到啦为止碍。如果梅需要杨计算提网络抽中从拔起点s到终弄点t之间写的最厕短路伞径，酸并设S(堆i)和T(说i)分别逮表示勺从S到顶烘点i和顶协点i到t的当展前最烘短路誓径长模度，P(析i)表示撤从s到i的当投前最辩短路阻径中柱顶点i的前愈驱，Q(内i)表示成从i到t的当宋前最亏短路卡径中批顶点i的后荐继，ds叶,d萝t分别口表示砌从s,竿t出发舟的当顿前最橡短路骄径长亿度，聚那么痛双向边搜索傻算法鞭可以臣描述箱如下:双向灶搜索他示意桨图1)设置众初值唱，令6.乐2.文4基于宴分层架地图掉的搜语索算浴法采用深多层休地图蚁的分宫级搜困索技今术可远实现环对搜删索空填间的底控制茎。基老于分御层地共图的镰路线泛规划仇算法俭对道浩路网苍络的框分层何规则裕要求蚁具备那以下谦特点仔和假伤设:(1圆)针对励不同冈的优关化标想准，首层次党可以仙按照托道路幅等级平或者宜预计萝的行垦车速蔬度进采行划层分;(2你)层次伐细节苹由高泰到低劳逐渐续增多危，高匙层次池是低冶层次父的子丹集;(3住)每个止层次移的道般路网章络是飞连通鸣的，阴对于墓低层话次这践是肯忌定的圈，在语高层悼次中涌大部雀分情自况下抱也是尖连通匆的,如果白不连弹通，敬可以议通过闲将低败层次穿中的蔽某些滤路段煤提取揉到高析层次沃中,使之哄构成斗连通旺的网并络。一种邪分层汪规则厦是按彻网络慨中的慎路段纹等级酒进行甚划分疏，如图6.扣4(戏a)所示轨，算典法在糟递归谅运行咽过程疲中总发是从累低层己次向牲高层爽次上码溯，顶使得点算法挖运行雀有时择会出估现舍葡近求胜远的脂不可版靠解牢。可步以这半样对影分层晒规则附加以原修改:如果雁两个砖层次西上下峡毗邻仔，则签在高界层节疫点集截中存尝储公医共边雁上的休毗邻感低层蚊次节拆点，唐如图6.迫4(误b)，这违样使量得算艰法在基递归精运行服过程悔中，歇能够冠找到纲更为远合理革的高中层次每邻近前节点阁，求掌得的该最优苹路径书解更蜻为可岸靠时闭增加奥了空海间存睡储。6.袜4道路旷网络苹的层绞次划锁分以构拒造分勾层地慰图搜始索算似法，真给定虏起点s和终夜点t,阴i申1、j1分别冠是包桂含s、t的最怒高层划次，普记为Si估1，Tj拴1，假曲设将贱道路债网络装划分泽成N个层茧次1,服2,脊…，N，则沾最优日路线则规划鱼分层桨搜索钓算法筒可以恐描述铅为：1)如果i1串=j殿1=工N，则s、t都位劳于最隶高层妈网络拼，直马接在N层道秧路网尾中计起算最愚短路假，结禽果即壤最优骑路线Si蔽1=妇SN-魄>T编j1坡=船TN;2)否则艘，如校果i1燥<值j1，必食有i1扰<盈N，找讨到距计离Si最近湾的上横一层午的节岗点Si动2，如爬果i2律<j议1,继续众寻把找距亩离Si齐2更上妙一层敏的节再点，技直到替寻找勒到节顷点Sj秘1,。3)如果j1着=N功,那么饲分别土在第1,陷2,优..播.,毙N摧-1层计沉算最临短路Si携1-戒>S素i2均->其…影SN-拨1->拆SN,在N层计近算最稻短路SN->挥Tj贤1=嘉TN，依烂次连此接最庙短路景，即晚得最拦优路元径;如果j1攻<围N,且Sj问1和Tj缝1处于煌第j1层的愿同一漂区域粘，那柏么分崖别在域第1,驶2,纯…，j1层计企算最反短路Si身1-乱>始Si巩2-朗>,律…,笼Sj口1-白1-顺>S干j1孤,S穴j1授->主T坑j1建,依次跪连接友最短毅路，饺即得扭最优怜路径;4)如果j1鞠<N太·但Sj惑1和Tj状1不在诉同一所区域梅，那劈燕么继鹅续寻劲找距稿离Sj麻1更上贼一层仅的节坏点，嘴寻找叫距丝式离Tj狸1最近滤的上当一层陆的节估点，唯直到颠寻找公到节考点Si万p，Tj宗q满足ip＝jq＝k,且Sk和Tk处于贺同一西区域初内，特或者k=辆N为止;5)然后怒分别购在不量同层剂次的妈道路得网络吼中计细算最阿短路Si字1－>Si昂2仗,…牌,S魄k-功1-痛>Sk舟,S尽k->Tk划,T蛙k->亿Tk宜-1木,…态,T巷j2色->截Tj娱1,将以欠上最谈短路转径依首次连纵接起暮来，腐就构揉成了接从起贩点S到终猪点T的最辉优路j径。对于j1丙<纪i1的情豆况，沫也按教照以伪上方港法进舰行，获这时累必须举首先迷向较棕高层浊次上席溯终饮点t。需要膜注意互的是奴，这帜种分泉层搜池索方咬法在脑高端塞层次周逐渐偶回溯柿，如辣果按脊照距缴离最济短的践优化芹标准猪，那璃么求吨得升的最档优路谷线可收能并想不是牧真正约的最疤短路两，因楚此是种有损屡算法砌。但引是一珠般的幻玉驾驶往员更跌喜欢雾在等划级高隐或者范速度栋快的扯公路驶上行垄驶，搬这种损结果男反而社是更锻优的兽。由于纯基于烤分层慌地图猜的搜逗索方贵法在铲起点S1和终扒点T1附近短寻找裹高一卖层的狭邻近讨节点S2和T2，将废路线扭规划功过程袭划分尤为几召个最塌短路绑计算富过程懂，从侧图6.讽5中可妥以看夕出，口低层骆次的游节点不规模龟庞大自，但秤其搜叙索空戚间C2容,烫C3大大硬减小源，而碰高层答次的闸搜索宪空间C1独,虽然羊和Di击jk过st惨ra算法孟的搜肌索空指间C0接近皱，但辈其中见的节蓝点数品目大抢大减折少，风从而跟提高复了算末法效僵率。6.轻2.尘6仿真墨试验需结果逃与分杂析利用Em莫be孝dd板ed哨V蜻is练ua城l须C涛++编写鸣了最圈优路摸线搜介索程挣序并招进行房诚了仿疲真试足验。排程序妨分别卖按5种方镜法搜躲索最可短路肢径，蹲它们交是:传统Di搂jk堵st具ra算法驱、应灶用四守叉堆陵运行镇结构盈的改循进Di寺jk剥st投ra算法毁、应据用四挣叉堆绣的A*算法劲、应判用四闸叉堆惨的双液向搜箩索A*算法们、应易用四防又堆烦的双臂向分易层搜慰索A*算法界。机蚁器主否频20斤6M姥Hz，内健存32很M，共旬进行怨了两吉组试屯验。第一忆组采冰用的格数字须道路结地图萄是北买京市带五环凭以内察的城控区图朵，共32色17旷2个路租段，12留56恐2个顶菌点，猜按照把道路犹等级接将地州图分贺成两子层:主干遇道为贡一层(高速佛、环滥线和谣快速涝路)，普姜通公侵路和股胡同枣为一厉层。踩这组地试验侍中每嚼种方蜜法分析别进殊行了5次试艇验，往它们化分别颗穿越童地图舅的约1/负5,养2经/5摘,晋3/刺5,帖4惕/5和整田个地搂图，补即这5次试捏验起时点和毛终点继的距危离越涉来越蹦长。第二低组采搁用的讽是部招分全弱国数矩字道剖路地朝图，横包含究上海夸城区播图(2担82久65个路拖段，10热83衡2个顶抬点)、杭楼州城亡区图(1睡87逗65条路润段，71厚36个顶程点)、南青京(2摔22邀93条路斯段，84挂71顶点)、宁胃波城窑区图(2思0椅54亚8条路饺段，81总82个顶眠点)以及削含有汁高速绿公路梯和国野道的袋全国碑道路大地图(1享57耐13条路润段，61崇67个顶更点)，每疾种方僵法也亚进行役了5次试秀验。表6.涝1北京插道路阀地图烫中儿妙种路诉线搜补索算浪法运反行时菠间结楚果(单位:5跃)表6.剂2全国漆道路扇地图炸中几溉种路铲线搜或索算释法运携行时下间结添果(单位:5倾)在引聚入四救叉堆颤运行旧结构吓、A*算法冒、双播向搜丈索和植分层遣搜索匆后，终算法叠的效吵率得晕到了舰很大现提高添。特尤别是亡在全凉国道烘路地迷图中路，分围层搜姨索的餐引入守对算秆法效斗率的正提高政有显食著作络用。由于洲分层踢搜索今在高播层搜毒索中抬忽略童了低粪层细烂节，额所以项最优勿路线赔不是免最短驰路径毫，而纤是更删多的型选择灶了高悉层次售路网捏中的远主干丑道，咬这也肺符合饲一般钩驾驶预者的绘喜爱纺。6.升3自主柔式车窗辆导蜜航系识统的洗设计人迅机俯接守口地图底显示地图台检索路径纽奉规划路径市引导地图怎匹配电太子逼地东图漆数达据GP规S数据挎解析DR传感男器数椒据解小析速率传感俩器角速顽率传颗感器图6-浅6车载甩定位牲导航肺系统米的系牢统结彻构我在捡哪里炮？从出绣发地幸到目叼的地扑的最访佳路私径如何疫到达稼目的撤地？附近推有无逗加油俗站/停车鸦场？实时贫地显虎示当横前莲位锹置路旷径称规愿划路勤径慕引核导附近斜设施逃查询*电酱子地迷图数刷据*GP拨S/禽DR信号台解忧析*地满图镇匹倘配*GI妻S空间原分析*拓茎扑分唱析*检仅索服记务点政信息*GP拴S/终DR信芽号允解烛析*地公图糠匹奔配*检秆索撤道路舰网各络信而息用户乌的问向题导航垫系统追功能应用耀的技把术图６-７导父航系矩统的蛇功能裕解析6.迎3.摔1系统营总体烤设计设计葵自主队式车竟辆导挺航系价统时炒需要啄考虑款的具头体因蛋素包刻括：系统课的单文位成裕本、每所能细提供件的定率位精存度、甩导航恼功能少的复附杂程舒度、耕是否辰需要夏无线躲通信籍系统圣以及暮是否俯需要完其他斥特定松的功压能等躺。典型胆的自共主式鸦车辆射导航奥系统虚应具倡备的解功能立：(1葱)系统惯能在90段%以上劲的行末程时嫩间里码确定岸车辆肠的实兵时位晚置，笨与实似际位甩置的冷偏差互应小愧于20吴m;(2趣)能够骗将车躬辆的丘实时缓位置识转化洽为地洗图坐打标，淘并与船道路欠网相矿匹配歉，以搬提供勾车辆轿在路雁网中知最可摸能的懂行驶示路段篮以及省车辆狂在路洗段中肯的具农体位砍置;(3嚷)系统喂能向释驾驶善员提途供以唯地图捕为背秩景的自图形轻化实窑时车夏辆位周置显桂示:(4际)系统图能接抢受行拦驶目影的地怀请求歌，按孟照合遥适的内规划佳标准赞给出厨当前脆位置妨或者占指定馅位置即到达具目的紧地的夕最佳余行驶暮路线惑；（5）系斧统能拼根据帜已经沿规划谜好的徐行车失路线吴产生养实时巴的引慨导指晃令，似并以北文字斧、图赠像或启语音茅提示(或者役三者宰混合)的方秃式提酿供给城驾驶蜂员;（6）系就统能啊确定邀车辆再当前巡寿是否兵偏离查了预咳定行蓄车路艳线，笛并及垂时作露出处脂理。（7）能嗓够通毁过多刷种方淡式如胃分类日查询析、拼旺音模临糊查帜询等姓，检梨索指杨定目简的地仅或者序兴趣辨点的科位置茫，也蚕能快悔速查横询指泻定位栗置附雨近的理各种训兴趣守点信幼息。设计象考虑郊到以将下几俘个原谦则:I.可靠惕性原呢则:系统汤要充膝分适阔应车牧载环易境的冒恶劣舅性，帖系统蹈必须捞稳定裙可靠馆。2.易用赵性原羡则:为加放强产接品的折市场黑需要兆，系突统的尽操作练过程疗必须仅尽可材能简仁单方倍便，成硬件贷接口映和软歪件操受作简挂洁明祸了，悔用户生界面贤直观浇友好乞。3.经济团性原完则:在保侧证完陷成实耳现目理标的单前提拴下，稍尽可直能优字化方尼案设哄计，躁精简抄系统悟的功搜能刻部挥件夕，匹降凶低单助位产碰品的挤制造弟成本辟。4.灵活悟性原批则:系统哀硬件卡具有题可扩闹展性鞋，系车统软显件要愚能够站方便怀地升烘级，黑在预廉期的孩产品陪生命仇周期懂内能樱够适莲应市遗场需扣求和贺运行秤环境愈的变芒化6.蚂3.遵2导航芳计算邀机系弟统设遗计硬件章结构挑设计图6.８蹲车辆坏导航蹄系统棒硬件季体系萌结构导航羽计算讨机是僚车辆溜导航携系统记硬件译体系欣的核添心部争分，催导航保计算潮机的欺设计幅要求鱼符合荒下列抵要求:具有穷复杂龟高速雪的运诊算能彻力，夜满足拘地图斯刷新恒、定管位计貌算、阵路线亡引导毕等具渡有较平高实写时性皱要求壁的计副算任奔务;具有研大容旦量的坛程序的存储智器(F及la络sh桃)和动石态随寻机存高储器(S梢DR栗AM懂)，满激足操蛙作系婆统的横运行溜要求巴以及适显示来缓存永的要饰求;具有坏便携渴式的管可移旬动存赖储介辅质，包满足物地图锹数据秋升级豆更新忘方便芦的要灯求;具有于高清逢晰度脑的彩梨色显第示能估力，闭满足级图形肯文字妻显示耻的要克求，数且要竹求显价示接分口标扮准规叠范，叨与其校它娱蛇乐系炕统的住显示慨兼容;具有会语音禾输出脉的能惊力，顷能够州实现外语音丝式引导最和操镜作提冤示;具有质各种巧串行咬接口秃，能缴够与枣定位顺模块朝、无育线通嫂信模即块、普控制制系统蹲等连越接，处同时依具有IO扩展止以及AD扩展耗的能皆力，满足锋系统忙控制决外设怠以及静升级壮的要勤求;最后芽还要芦求整悟个系裹统稳歇定可掩靠，键连接耍牢固塘，满文足车在载环勒境的旁恶劣近要求耐。硬件生系统婶一般出采用岩嵌入弓式计悼算机泽设计士方案冬，如膀图6.９所套示中央捆处理染采用哪的是森基于AR物Mv气4内核糖的In顶te章l公司斗的St于ro某ng越AR才M.避SA袜11掠10，除美了采附用高荒性能百的CP纸U以外欢，连墨同32伙M的SD膏RA谦M和32珠M的FL晨AS曾H一起边构成军了系喜统内猜核;同时弃，计烦算机佣系统岁还具倚有SI弓D1毅38死06构成炭的多闷模式2D显示诞加速落模块;由X3饱03集2,右1疫62准44败,1罢62神45构成射的总吸线缓榴冲模沫块;16困23哲74构成离的板颈上状简态/控制位寄存验器;语音钢输出话功能跨由Ph温il川ip冰s公司响的UC答B摧13醉00来实唤现，最它的胳语音竭处理时功能颜可以腹实现会录音眠和放啊音，昌而月傲利用弓它的AD功能尸能监祝控主故板上于的电蛾压和瓶温度;通过溜系统括总线禾，将谈两路UA饭RT串口段，多异路GP腐IO信号轻以及UC屯B蛛13鼻00提供超的触晚摸屏/A触D信号悟集成尿起来忽。图6岗.9基于In父te累lS柜tr萝on葛gAR少M增SA贵11俭10的导湾航计贼算机专结构6.吩3.草3软件葵体系声设计根据久系统佣功能莫的要绩求，近整个朗软件梳有两受大部辜分:操作低系统看和应猪用程商序。图6－9自主贷式车卡辆导窑航系卷统软沈件体声系结层构在软必件体娃系中宜采用顶分层镜结构叉使得锻应用垫软件辅具有略硬件始无关浩型，皂即不悔依赖践与具布体硬策件的圾独立粪性。无关彼性有拨两层上含义：一、肤系统广中所蔬有的戏硬件撇设备遗都由眨操作榆系统侦接管愚，应些用程石序不客直接门对硬剂件进辞行访各问。二、扑所有持涉及因硬件晚的操抵作都屡通过阔调用瓜标准青的AP贩I函数匠来完写成。这种衔无关笑性极帐大的餐增强劝了应罚用程秀序的否可移直植性蒙，为买系统剩的软掩、硬卫件开棋发、专升级眉和改筝进带拆来了盘方便抵。操作胡系统搏是构磨建整填个软浙件体脂系的站基础织目前府比较抄成熟找的操裳作系灯统有期很多庭，其竭中嵌冒入式坦操作日系统础随着窑计算疏机技君术的牺发展匪也出龟现了断很多答种，拿比较野有名袜的有Em刚be吐dd探ed仁L扛in免ux境,蜓Wi昏nd迎ow缸s略CE廊,Vx低Wo及rk阻s,慰Pa直lmos等等刑。这怕些操狠作系匀统各罢有所描长，溉支持童的CP菠U以及卷函数宜功能斥也各寇不相愤同。选择读操作枪系统茫的要租求:1、窗为满统足系惨统功牧能的福要求净，操剂作系震统应事提供聪良好幅的图沟形显肾示支福持和坑强大葵的多遵任务棍管理棋能力;2、棵为适容应嵌像入式督硬件风系统比，操董作系揉统应猫体积春小，犁可以傲按用广户的司要求过来增仓减功益能。昨这样蝇才跃能丽最晶大携程弦度地愧去除版不需箭要的密冗余掩，节表省存畜储空福间，欺同时忠也要舅方便庆用户隙自己佛的坑功旧能仅扩堂展城。3、从善应用纱软件翁开发彩的角足度考领虑，思应选镇择开熔发平电台功胳能强购、共酸享软刊件资希源丰影富、撑支持搬多种坛嵌入嗓式硬累件的碰操作缝系统;4、从诊适应扁恶劣挑的车蜡载环血境考哑虑，虑操作楼系统馅必须挥能够起脱离恋硬盘足，直勾接从RO叙M/餐FL威AS习H中启先动利，对栽内存东开销殊、存林储容茅量等铲硬件赢资源散的需背求应拨尽可淡能低威。5、从奖用户阵使用镰的方菌便程侮度考消虑，忘要求号操作样系统我支持蚀即时还关机症，另治外也庄要考荡虑操率作系搞统门的扬成缺本蛇。Wi络nd倍ow销s摆CE是美使国微刘软公汤司开补发的若专门乐为各倘种移垄动和收便携根移动己电子优设备衫、个缝人信探息产插品、脂消费捕类电甘子产扒品等在有严附格资惰源限话制的犬硬件筒系统槽设计病的一蜘种32位高许性能涂嵌入傍式操齐作系铲统，定它有李一个伐简洁演、高赔效的拿完全茂抢占锹式多企任务欲内核飘，支粗持强端大的抗通信惹和图岛形显浙示功梦能，关能够关适应枣广泛胖的系肆统需除求。Wi资nd遥ow裹s雨CE系统惭的主汤要特猴点包六括（5点）1)兼容穷于微脉软公阁司的众视窗(W海in泼do夸ws智)电脑易操作火系统口，支岛持多部种应佳用程郊序编加程接局口(W步in颠32冤A罗PI次)函数;2)提供数最广览泛的徐硬件兔支持聪，包井括通号信接排口、窜高分社辨率泼真彩另色显倘示和勾打印剪设备脂、输糖入输落出设右备果、旦音敏频设桑备、勺网络武和存球储设进备等;3)支持办数十粗种不钟同的32位微疼处理斥器芯刺片，悲如:I雾nt宵el和AM搭D公司轿的x8体6系列盗、摩绝托罗坦拉形公司灶的Po阁we跟rP僵C、日遮立公坊司的SH梅3系列兼、东肤芝公质司的MI蠢PS系列苹等;4)采用拉模块遮化结晨构，骑配置融灵活阅，运针行时疫仅需守很少码的存雁储器(R援AM谎)资源合，并管且可饭以直批接从盆只秒读存面储器(R垂OM裳)中启筐动和赔运行;5)微软蒸公司渗为Wi脸nd雾ow扛s庄CE的开趟发提睡供了遍一套松完整处的功丸能强索大的狼系列勺工具忧，从薪硬件疗调试铁到李软痰件盒开发剂都为筹用户饶提供宿了方住便。Wi佩nd纹ow净s哀CE是目吨前最震强大粱的嵌美入式织操作机系统盯，所印提供慨的功色能包惑括系统晕与应激用程策序的失初始右化与竟同步俩管理析、内寻存管蹲理和据分配钩、系昂统时障钟管趴理、染设备死驱动造管理烘、程朋序进麦程间本通信好和数恐据交泥换控控制、善磁盘万和文热件系串统操锻作与影管理持等，wi氏nd韵ow迹s砖CE操作绣系统结是车牛辆导粪航系层统应训用软苹件运厨行的波理想茂平台块。Em脉be械dd投ed某L份in瓦ux的开作放源辞码特牌性，休它的仗可移衰植性接和可钟扩展厅性提息供了份最大雄的灵辜活度芹。但弄开发逢工作沾量很说大，觉目前兄还没润有一怎家能轰给出滩一套键从硬誉件到礼软件纠的完位善的妖开发掘调试吼系统概。Li识nu机x在图吉形功升能的评支持态上也瘦差强抢人意宝。长迅远来族看，Li镇nu椅x的公赶开和励免费打，使矩它具言有强置大的棚生命敏力，段它的馅功能严也会亲在众丑多开退发者柱的努腾力下鞋日臻配完善踪蝶。6.两3.债4功能执子系绵统设屯计1、定恨位子锹系统定位划子系蚁统是油车辆久导航混系统浓的重常要组摧成部偿分，洞它包做括定乎位模氏块和雪地图蛋匹配够模块俩，为爱满足抱高精仰度连细续车构辆定阳位的为要求脏，最勉佳的攀定位域方式肃是组朝合定加位。考虑桌到整削个系蛋统的姥不同准成本亮和档幅次，幻玉以及拘安装耳的复季杂程孙度，彩在设躬计定异位子板系统熟时在先不同顾的系处统中稻采取疤了不磁同的天组合样定位陆方案锡，一融种是GP普S+强MM，为钥了便晌于功迁能升驳级，俱预留谅了DR接口盲，另读一种烧是GP胃S十DR古+M史M。如魂下页依图6－11所示碌。图6－11蜘G连PS十DR氏+M眉M组合幻玉定位乞系统灾框图GP裕S+容D间R略+M痛M组合爱定位汁子系然统首莲先在们每个大采样抬时刻k=nT由扩夏展Ka划lm非an滤波号器处很理DR传感师器和GP勉S的量歉测数步据并备给出络车辆厨位置尺估计捐、行垫车方蝇向估蚊计以役及定因位误凳差估墨计;然后窃将滤笼波器虎输出梳的这常些最贴优估序计输蔽入到润地图叠匹配扶模块作，由权地图悉匹配爷算法骡计算证出当吓前时稍刻的炸匹配颤位置法坐标管，即士为车签辆当嫌前的垂位置畅输出龙。2、导计航子碌系统导航潜子系某统负乏责完险成车耀辆导蒙航功衔能，培包括启路线禽规划悟和路锐线引拘导，级前面老已经尖讨论讽了论歌了路坊线规每划算啊法的碎设计浙与实永现，浑而路威线引叮导则崖是指块挥驾揉驶员住沿着纳路线煎规划娃模块仓计算辉的最民佳路早线行轿驶的涌过程帆，它司包括续两个从任务:一是哪产生漂行驶臭引导核指令斩，二字是跟怪踪车敬辆在秩规划曾路线莫上的寄行驶瓣情况军。路幼线导门航子组系统约与其牌它模掠块的盐相互还关系玻如图6.屑12所示扩。6.丽12路逆线昆导石航静子但系美统与其罗它辣模开块兼的堡相互率作储用图6－13表示拢了一同种引吩导生酿成算件法，杠其中秤的角关度标找注代筐表两户条相秃邻路涉段在喘交叉打点处胸的取暖向角既差值篇，顺纯时针欢为正等；路慨段取地向角色定义险为路象段取喷向与蕉正北项方向垦的差趋值，脱取值确为0～36担0度，叙引导旅指令库产生承后就场是实淘时监处视车慈辆在逗预定杂路径纽奉上的烟行驶胳情况凑，以搜确定犁什么第时候推向用龟户输粥出引呢导信坦息。将引声导信橡息分汤为三关种:早期射提示眨、准龟各提平示和纠到达遭提示熟。早期但提示夏在车困辆通绳过上楚一交送叉路浇口后送给出甩，通燥知驾弓驶员颠在下破一个朵路口岂所要滑采取妥的操抢作;准备初提示筋在车志辆进骆入距涝路口垫一定散范围蹲内的咳区域距时给卷出，呆提示完驾驶陶员做点好操热作准栗备，虑注意件路标被、出摩日标辽记等发有关俯交通巨标志拴。到达码提示削通知速驾驶封员已品经接侨近交滴叉路说口，骑注意呢执行塔引导乱指令套。动态浅导航另的另踩一个辩重要友内容丢是车造辆偏屿离预雅定的尤路径。处估理方胖法：峰一旦随系统淘确定虹车辆考不再卸行驶晒在给接定的旺路线绩上，产系统监必须收先对找驾驶货员给荷出提左示，蕉同时姐在屏披幕上唉只是阶预定王目的各地的贫相对言方位面，以客方便努驾驶柴员能俊返回彼原来插的路阅径，小当一狐段时今间后眉车辆摧仍然箭没有农回到此预定饰路线扭，则你重新纯规划宴一条驾由当挑前车庭辆位衫置通须往目多的地膀的最滩佳行泊车路族线。3、人睁机接创口一个改完整壤的车崇辆导鹅航系挺统，滋必须增具有充良好全的人巴机接晨口，槐它提便供用译户与秘导航芝设备愿的交渡互。贷地图并与车喇辆位廊置显驻示、训路线坛规划隶、路鸽线引冲导和表其它硬活动识的各象种不立同要寨求通狡过人敌机接俯口传岗送到倒计算存机，壶并且牌反馈恰给用奴户。人机监接口王包括帽两个橡部分:输入呆控制拿部分膨和输戚出部顿分，其中习有些候接口厕与其喂它汽犬车电水子产劈燕品是腔兼容景和共惹享的匆。（1）输蜓出接产口输出闪接口妻是向停用户榨提供晴与车迈辆导轰航功洞能等霉相关撤的信令息手度段，举视频言和音顺频接卫口是菠两种刘最常忙用和时有效浇的手哥段，种因此衡在设锻计输鞭出接值口时缝，可则以采牺用高踏清晰别的真驴彩TF判T甘LC四D显示途器，嗓车辆反行进县过程万中某沃一时眨刻显滚示器壤提供光的可视视内努容包恭括:彩色迟数字梁地图滋，车遭辆的邀位置影点，浙车辆穗行驶酬方向骑，当胜前行堂驶的驻道路否名称天，最舟优路杀线的拜突出钞显示臂，路率线引颈导过致程中谦的文饼字和阅图像臣提示(如拐淋弯方蛮向，躺重要换单位中等)，到钥达目坟的地希和下酷一个印提示案交叉或口的传距离故提示符等等虏。为了束避免泥分散规驾驶个员的美注意络力，父从而哗影响佳安全农驾驶禁，因摇此系得统还暴应该岔具有睬语音届输出盐，并季且语枣音输驶出的白内容遇简短甜而有暮效，蓬主要价内容写包括:操作罗提示禾、路慌线引漏导指畏令、独超速霉提醒训、当辛前车丛辆行嘱驶道横路或合重要戏兴趣报点提及示等给。（2）输余入接逝口在设净计车芒辆导隔航系通统的戚输入影控制暂系统驾时，奴主要铃强调恼安全姐和操硬作方计便，帜首先稳是提怨供多是种操添作控港制方飞式，没包括鸦红外碑遥控挣、按挖键和舍触摸吸操作捆方式境，任卡用户交选择呈使用药，其身次简纯化各介个功绿能的萝操作隶过程年。（3）导剪航和质娱乐你共享锣部件近些搅年来李，柴汽车姓信息逐电子疼设备河发展焦迅速抄，它雨们现虹在已各经被纯集成齐到车去辆结茅构中疗，作颂为复渣杂电载路的锻组成捷部分努，如剥汽车踢音响皂、汽庄车VC若D/厚DV蔑D等，厕因此攻车辆思导航匆系统甜的人楚机接迁口要消求标订准规取范，令例如往视频盲设备系既可躲以用改来显撞示导荡航地隆图与仗信息卵，也击可以套用来储显示VC叠D/殊DV疗D图像交或者TV饶;存储株设备许既可录以用悬来存夸储地受图，振也可耳以用石来存腹储MP若3音乐另等。旬将车东辆导脏航系具统与静这些皱汽车炊娱乐碎设备火集成冷到一教体也客是汽棉车电恐子信泊息产满品的爷一个鹊发展糕趋势狮。6.裹4中心撒决定亩式车填辆导就航系辨统的渣设计中心蒸决定言式车设辆导六航系雹统具郊有的白特点顾：（1）利亏用信宵息点期指令司处理型机制漫来实朝现终寻端的盈多种术功能蔽。（2）终归端不章需要车存有驼地图缸数据遍，节庭省了膏大量毙的存奇储资陪源和泳运算怜资源秋。（3）路要径规头划在烦中心墓进行盐。（4）能旋够提者供信臭息采绝集、构信息牵服务详等多乳种增骡值服情务功脂能。（2）具疮备成谦为车饭辆导锡航器腔、车浸辆黑依匣子籍的硬篇件平线台的赤能力弓。6.愧4.丑1系统充组成脂及原扫理三大榆部分蒜组成拘：控制悼中心气、车载寨导航菜终端通信束网以GP影RS作为给通信颤系统蚂组成眨如图6－13所示逐。控制董中心维主要块由网碑络服鼻务器无、数继据库侧、显历示终往端组怠成。完成浇功能努：指湾令下抹载、滑信息艺点数恨据管救理、浑实时胡监视焰、路闯径导滑航等水功能晌。车载帅导航透终端谊主要念由嵌筹入式算处理彩器模剃块和GP线S模块园、GP眼RS模块工等组那成，田且包大含一地个独刊特的很指令苏系统跃，根抵据信杜息点临指令荷来执烤行相黑应操骆作。信息尸点具忌有多恩种形锐式：需位置其型信福息点源、导讽航型射信息阶点、虏信息复服务恶信息该点。位置业型信舍息点爆的指宜令执槐行过付程如蓄下：锁当车糟载终川端上日的GP扭S模块竞输出剂的本租车坐驰标进典入存播储器伏中某呼位置王信息拒点的伟坐标扩有效滥范围赔时，毛该信皮息点遣指令她满足赴执行碰的触宏发要屠求。营中央灿处理婚器（CP稠U）将潮“向刺中心矿发送梯信息袍”作敢为指迎定的码操作续类型萝，将虾本车舒状态两信息意，包柱括当抗前坐脱标、芹本车原速度故、方胡向等生信息员作为膀该信拉息点刮对应拾的操羞作内蹦容、云完成剪该指剖令操恰作，边从而降完成蝴信息有采集蓝任务碍。6.嘉4.仓2系统香设计1.车载赛终端呼硬件棒设计主要粗由嵌符入式裙处理霜器模棵块、GP葛S定位制模块凳、GP揉RS通信嚷模块秆、LC得D显示鸦模块财、语虎音模满块、茂电源机控制煤模块嚼以及丘扩展奇接口柴模块怒等组田成。如图6－14所示举。核心鼠为：处理逗器模挎块（1）处辟理器驾模块功能叙：处理勒器按谜照一仰定的办指令妖类型西对车栗载终矛端存干储器强中的悲现存际指令绒集进锋行轮腿询，婶每个丝式指令袋的触懂发条汇件与黑现有祖车载戚终端邮所掌目握的份本车歪状态周进行杯判断歌。当造判断习某条碑指令佩的触演发条肉件满坐足时斯，执神行相福应的溉操作陵。硬件抓组成肯：由嵌寄入式CP登U芯片湿以及桃外围悟电路龙存储兼模块尖（FL谨AS就H、SD骡RA危M）组翻成，FL惰AS杏H用于钞存放登嵌入色式操促作系阀统，晃而SD躺RA很M用于甜存放猾导航竹应用梅软件然和指徐令数齐据。（2）显兽示模签块功能臭：用户情通过舍触摸杂屏进翠行各姨种个墓性化屑服务恶设置胜，路乖径引膜导线尤路等来的显那示。硬件艇组成配：液晶竹显示绿屏以云及LC暗D控制水器组排成。（3）语裹音模碑块功能否：在冈处理贤器的惑控制等下，达对文端字信此息转迹换为存语音伪信息数，通煎过与貌语音良接口碗扬声脑器设抵备播把放出景去，略利用脖语音财对用趣户进梁行导樱航和颜提示蔑。组成微：语沸音合姥成芯记片和迎语音训接口缝。（4）扩笛展接泽口模充块为实罩现功缘瑞能扩写展设方计，恋主要飞由A/蝇D转换牢模块软构成巩，预绘留有GP劳IO口（籍可用疾于中回断）躲和A/愤D通道越，通捷过它未们可乒以处弦理开明关量怒的