【正文】 以盲人導(dǎo)航系統(tǒng)的數(shù)據(jù)庫并不需要有正常人使用的界面及道路位置等信息，只需要知道道路之間的連接關(guān)系即可 。 文件夾后通過 configure 腳本生成 Makefile 文件： ./configure disabletcl prefix=/home/sqlitearmlinux/ host=armlinux makefile 文件，進(jìn)行編譯并安裝： make amp。它支持 Linux 操作系統(tǒng)，能夠通過 C語言進(jìn)行很好的結(jié)合，更重要的是，它的數(shù)據(jù)處理速度比 Mysql、 PostgreSQL 等知名的數(shù)據(jù)庫管理系統(tǒng)更快。根據(jù)這三者，對原始的最短路徑算法進(jìn)行改進(jìn)，以達(dá)到更好的適應(yīng)本系統(tǒng)的需要。其系統(tǒng)結(jié)構(gòu)框圖如下： U P T E C H P X A 2 7 0U S B 接 口U S B 接 口U S B 接 口U A R T 接 口A C 39。其包括手持式終端、盲人手杖和 RFID 標(biāo)簽。先進(jìn)行道路等級的劃分、對道路權(quán)值的計(jì)算后通過 Dijkstra 算法得到最短路徑，從而實(shí)現(xiàn)最優(yōu)路徑的選取，并 通過以上的設(shè)計(jì)實(shí)現(xiàn)如下功能： 1. 盲人出行時(shí)自動(dòng)讀取盲道上的第一張標(biāo)簽，確定當(dāng)前的地理位置并通過語音提示的方式通知盲人 。 主要由于我國的 相關(guān) 基礎(chǔ)建設(shè)不 夠 完善，盲道 的 管理不夠規(guī)范 ，經(jīng)常出現(xiàn)盲道被占用以及盲道連通性不足的情況， 并且， 國內(nèi) RFID 技術(shù)的不成熟以及 研究 該方面 系統(tǒng)的人員欠缺等等 也 都是我們目前 需要解決的 問題。 最短路徑算法是 圖論中 長久以來的經(jīng)典問題， 它是計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)、交通工程學(xué)、地理信息科學(xué)等學(xué)科的研究熱點(diǎn)， 從 20 世紀(jì) 50年代至今一直被廣泛研究，它在交通運(yùn)輸分析與規(guī)劃研究中是一個(gè)必不可少的環(huán)節(jié)， 目前Dijkstra(迪杰斯特拉 )算法是典型的最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。 該研究計(jì)劃由歐盟資助 ，旨在為盲人 這一特殊群體 開發(fā)基于 RFID 的道路 信息 指示 。而 GPS全球定位系統(tǒng)進(jìn)行導(dǎo)航則存在著一個(gè)精度的問題，最多只能提供一個(gè)大概的地點(diǎn)，而且存在著危險(xiǎn)性 。 黨和政府歷來十分重視和關(guān)心殘疾人扶貧工作 ,中國殘聯(lián)成立 20 年來 ,通過一系列有力措施對貧困殘疾人予以扶持 ,取得了顯著的效果。 總而言之，求合理路徑集的方法就是盡量縮小搜索范圍，配合合 理的數(shù)據(jù)庫進(jìn)行快速搜索，從而得到合理路徑集。 承諾 人簽名： 日期： 年 月 日 Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) I 基于 RFID 的盲人導(dǎo)航系統(tǒng)路徑搜索設(shè)計(jì)與實(shí)現(xiàn) 摘 要 隨著城市人口數(shù)目的增加，盲人這個(gè)特殊的群體也越來越受人們的關(guān)注，盲人的 出行一直是困擾盲人的問題，尤其是去距離稍微遠(yuǎn)一些的地方，通常都會感到力不從心 。 本論文 提出了一種物聯(lián)網(wǎng)技術(shù)下盲人導(dǎo)航系統(tǒng)的路徑規(guī)劃算法。 最后 ，利用 仿真實(shí)驗(yàn)和實(shí)例分析驗(yàn)證了算法的正確性。然而出行 一直是困擾盲人的問題，尤其是去距離稍微遠(yuǎn)一些的地方，通常都會感到力不從心。 對于盲人這個(gè)特殊群體，由于轉(zhuǎn)彎次數(shù)、路面狀況 、紅綠燈情況 等影響，盲人所行走的最短路徑并不一定就是最合適的路徑 。目前一個(gè) Ispra 的歐盟公民救援與防護(hù)中心（ ISPC）組建的 10 人的專家組正在意大利北部的 LavenoMombello 測試三條植入 1260 枚電子標(biāo)簽的人行道 。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。 關(guān)于最短路徑算法的研究，除了計(jì)算機(jī)網(wǎng)絡(luò)通訊技術(shù)領(lǐng)域外，在交通運(yùn)輸方面也被廣泛研究，其中清華大學(xué)、中山大學(xué)、吉林大學(xué)、北京理工大學(xué)等多所高校都對此方面有所研究。 2. 盲人使用盲人輸入法通過盲人鍵盤輸入目的 地后，系統(tǒng)通過數(shù)據(jù)庫的查詢配合 Dijkstra 算法、矩形算法 等 生成一條最合理的鋪有 RFID 電子標(biāo)簽的盲道路徑并開始提示盲人進(jìn)行行走。其中，RFID 標(biāo)簽埋設(shè)于盲道上；盲人手杖通過 RFID 射頻識別模塊讀取盲道上的 RFID標(biāo)簽的信息；而盲人手杖與手持式終端通過無線傳輸模塊建立連接，用于將標(biāo)簽信息傳遞給盲人手持式終端進(jìn)行處理后給出導(dǎo)航指示。 9 7 接 口A T 8 9 C 5 1UART接口GPIO接口鍵 盤 模 塊G P I O 接 口紅 外 接 受 模 塊Z i g B e e 模 塊G P S 模 塊G S M 模 塊語 音 提 示 模 塊L M 3 S 1 1 3 8UART接口G P I O 接 口G P I O 接 口Z i g B e e 模 塊R F I D 模 塊超 聲 波 模 塊電 子 標(biāo) 簽路 況 事 件無 線 鍵 盤手 持 終 端盲 人 手 杖路 面 圖 21 系統(tǒng)結(jié)構(gòu)框圖 本系統(tǒng)導(dǎo)航問題的核心算法就是最優(yōu)路徑搜索，如何生成最優(yōu)路徑至關(guān)重要。 Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) 5 3 數(shù)據(jù)庫 實(shí)現(xiàn)原理 數(shù)據(jù)庫介紹 盲人導(dǎo)航系統(tǒng)需要考慮到盲人的安全問題，因此 它必須是一個(gè)實(shí)時(shí)性的系統(tǒng)，對于數(shù)據(jù)的處理 要求 盡可能的快速且準(zhǔn)確，數(shù)據(jù)庫的選擇和設(shè)計(jì)就起到了至關(guān)重要的作用。 SQLite 數(shù)據(jù)庫結(jié)構(gòu)簡單、操作簡單，無需安裝和管理配置，它支持?jǐn)?shù)據(jù)庫大小至 4TB，完全滿足盲人導(dǎo)航系統(tǒng)的需要。amp。 本系統(tǒng)所涉及的問題屬于非數(shù)值問題，必須先將盲道網(wǎng)絡(luò)轉(zhuǎn)換為計(jì)算機(jī)能夠識別和處理的數(shù)據(jù)結(jié)構(gòu)。針對上述問題，故采用關(guān)系數(shù)據(jù)庫的存儲模式。 RFID 標(biāo)簽可以根據(jù)標(biāo)志性建筑的密集程度來 鋪設(shè)，但是相鄰的兩個(gè) RFID 標(biāo)簽的距離不低于 1米，這樣有利于識別距離的設(shè)定（識別距離設(shè)定為 至 ，約為成年人行進(jìn)一步至兩步的距離）。同時(shí)，該表還描述了地名信息和 RFID 標(biāo)簽碼唯一的對應(yīng)關(guān)系。 printf(\nif the database does no exist we will build a new one!)。t open database: %s\n, sqlite3_errmsg(db))。 return 1。 char tem_sql1[256] = = Roadthird。 的關(guān)聯(lián)道路的起點(diǎn)和終點(diǎn) RFID 碼查詢該道路的完整路徑 ： char tem_sql[256]=select * from road where Roadfirst= 。 char tem_sql0[256] = and Prompno=。 sql 拼接成完整的 sqlite 查詢語句 范例 ： sql = strcat(tem_sql,name)。 Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) 10 4 算法設(shè)計(jì) 設(shè)計(jì) 算法介紹 解決單源最短路徑問題的一個(gè)常用算法是 Dijkstra 算法 [24]，它由著名數(shù)學(xué)家 1959年提出，是按路徑權(quán)值遞增的次序產(chǎn)生最短路徑的算法；可將本系統(tǒng)所涉及的盲道網(wǎng)絡(luò)簡化抽象為賦權(quán)網(wǎng)絡(luò)，把盲道抽象為網(wǎng)絡(luò)中的邊，并以邊的權(quán)值來表示盲道相關(guān)的參數(shù)，算法產(chǎn)生了賦權(quán)網(wǎng)絡(luò)中從指定的結(jié)點(diǎn)到所有其它結(jié)點(diǎn)權(quán)值最小的路徑。 最后，算法在將未確定結(jié)點(diǎn) v加入確定結(jié)點(diǎn)集合時(shí)，還需考慮如下問題： 1． 對于任意節(jié)點(diǎn) u有一對標(biāo)記 (du， pu)[5]，其中 du是從起源結(jié)點(diǎn) s到結(jié)點(diǎn) u的最短路徑權(quán)值（當(dāng) s=u 時(shí)， du=0）， pu則是從源點(diǎn) s 到 u的最短路徑中 u點(diǎn)的前驅(qū)結(jié)點(diǎn)。//所有節(jié)點(diǎn)都設(shè)為未知 } =0。 if(v==NOT_A_VERTEX) break。// 更新 du、 pu } } } 從上面 Dijkstra 算法的描述及實(shí)現(xiàn)方法可以看出， Dijkstra 的算法實(shí)現(xiàn)起來非常容易，由 Dijkstra 算法的偽代碼可以看出， Dijkstra 中存在三個(gè)循環(huán)，它的時(shí)間復(fù)雜度為 0（ n178。第一個(gè)選擇頂點(diǎn)為 U1，路徑長為 為 known。 Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) 13 表 43 U4被聲明為已知后的節(jié)點(diǎn)狀態(tài)表 U Known du pu U1 T 0 0 U2 F 4 U4 U3 F 3 U4 U4 T 1 U1 U5 F 3 U4 U6 F 9 U4 U7 F 5 U4 選擇 U U5加入確定節(jié)點(diǎn)集合后， U2是領(lǐng)接的點(diǎn)，但不用進(jìn)行調(diào)整，因?yàn)榻?jīng)過 U2的值為 3+10=13 而長為 4的路徑是已知的。再下一個(gè)點(diǎn)選取的是頂點(diǎn) U7， U6下調(diào)到 5+1= 如 46所示。 Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) 16 多因素模糊算法 多因素模糊算法的提出 一般情況下，盲人從當(dāng)前位置到達(dá)目標(biāo)位置所需要考慮到的不只是最短的路徑，而是綜 合考慮多種因素后的最佳路徑。而權(quán)值應(yīng)該看作由 距離因素和其他需要采用模糊隸屬度來表示的盲道因素兩部分組成 [7]： ),()(i s t)x,( 321n21 nxxxb F u z zxaDxxW ?? ?? (41) 式 (41)中， Dist(x1)表示道路距離函數(shù)， Fuzz(x2,x3,?,x n)表示如路面狀況 、周圍 環(huán)境 狀況、道路繁忙狀況、紅綠燈狀況 等非數(shù)值因素的模糊綜合函數(shù)， a、 b為系數(shù)常量，由實(shí)際情況調(diào)整。 對于每條道路，分別對 其 4 個(gè)因素進(jìn)行評分，得到它的評分向量 C ＝｛ C1，C 2， C 3， C 4｝，對于各個(gè)因素評分的標(biāo)準(zhǔn)如下： （城市道路類型）：優(yōu) —— 高級 水泥混凝土、瀝青混凝土、整齊石塊或石條。 （城市區(qū)域環(huán)境噪聲等級）：優(yōu) —— 噪聲 ≤ dB （好）。 （人流量，單位：人 /h）：優(yōu) —— 100≤ 人流量 ≤250 。 ：優(yōu) —— 無紅綠燈。由于其全向搜索，依然有大量的冗余計(jì)算。對于不同路況的地區(qū)， 也 可使用不同的 γ 值進(jìn)行計(jì)算。其基本思想是求出限制橢圓Xx學(xué)院 2020屆本科生畢業(yè)設(shè)計(jì) 20 的最小包含矩陣，以此作為限制區(qū)域，既減少了搜索的規(guī)模，又避免了大量復(fù)雜的運(yùn)算。 表 49節(jié)點(diǎn)坐標(biāo)表 列名 說明 數(shù)據(jù)類型 約束 Roadno 結(jié)點(diǎn)的 RFID標(biāo)簽碼 int 主碼 Longitude 結(jié)點(diǎn)的經(jīng)度 double 非空 Latitude 結(jié)點(diǎn)的緯度 double 非空 對于第二個(gè)問題，不妨定義比例系數(shù)γ = E / P [12]，其中 P為起始點(diǎn)和目標(biāo)點(diǎn)兩點(diǎn)間的直線距離， E 則為兩點(diǎn)的大致極限距離。final[v0]=TURE。i++)//將 v0領(lǐng)接節(jié)點(diǎn)對應(yīng)權(quán)值插入堆中 heap_insert(A,D[v0_adj[i]])。rn。amp。amp。 for(w=0。//尋找 vw 對應(yīng)路段 if(v==WayInfo[edge].fnode)//決定路段方向阻抗 c[v][v_adj[w]]=WayInfo[edge].ft_imp。jModeTurn[v].num_turn。(NodeTurn[v].to_node[j]==w))。對于不同的起點(diǎn)和終點(diǎn)進(jìn)行最短路徑搜索比較，限于篇幅有限，無法一一列出我校任意兩點(diǎn)之間搜索情況，此處只給出了我校 學(xué)生一飯?zhí)玫交堑乃阉髑闆r，如下： 圖 51 經(jīng)典 Dijkstra算法的搜素結(jié)果 圖 52 優(yōu)化的 Dijkstra算法的搜索結(jié)果 兩圖中的線條表示響應(yīng)算法在搜索最短路徑過程中所考慮過的盲道，而其中加粗的線條則為搜索到的最短路徑。