徐瑩　林佳珍

摘 要： 高效的公安系統(tǒng)決定著社會(huì)治安的狀況，為了能迅速定位犯罪分子并迅速出警，提出了“防盜追蹤器”的設(shè)計(jì)思路。在比較各類路徑優(yōu)化算法的基礎(chǔ)上，基于A*算法給出了最優(yōu)出警線路的設(shè)計(jì)方案。該算法成本低、搜索效率高，能夠充分提高出警速度與效率。

關(guān)鍵詞： 防盜追蹤； GPS； 出警； 線路優(yōu)化； A*算法

中圖分類號(hào)：TP277；TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2015）03-04-03

Abstract： The status of the social security depends on the efficiency of police system. In order to find the crime quickly and enable the police to catch the crime at the first time， a new design idea of "anti-theft tracker" is put forward. Comparing all kinds of path optimization algorithms， a design scheme of optimal police route by using A* algorithm is given. It has the advantages including low cost， high efficiency of search， improving both the response speed and efficiency.

Key words： anti-theft tracking； GPS； work efficiency of police； route optimization； A* algorithm

0 引言

社會(huì)治安狀況的好壞關(guān)系到每一個(gè)公民的生命與財(cái)產(chǎn)安全，能否建設(shè)高效率的公安系統(tǒng)決定著人民能否安居樂(lè)業(yè)。為了迅速破案，公安機(jī)關(guān)怎樣得知罪犯所在地并給出最優(yōu)化的出警路線顯得格外重要。在現(xiàn)代科學(xué)技術(shù)迅速的數(shù)字化時(shí)代，應(yīng)充分利用時(shí)代資源，如利用管理信息系統(tǒng)和運(yùn)籌學(xué)來(lái)進(jìn)行最優(yōu)線路的規(guī)劃設(shè)計(jì)，利用最優(yōu)路徑模型的測(cè)算和城市地理信息數(shù)字化來(lái)選擇最優(yōu)的通行道路，以期最終達(dá)到縮短出警車輛的路程所耗時(shí)的目的。隨著信息化的普及和發(fā)展，有效利用先進(jìn)的計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)和通訊手段，并結(jié)合各種高速發(fā)展的新興技術(shù)成果為公安系統(tǒng)服務(wù)已成為時(shí)代趨勢(shì)[1-2]。

1 貴重物品防盜追蹤器設(shè)計(jì)思路

目前，通信科學(xué)技術(shù)的發(fā)展帶來(lái)的是通信導(dǎo)航全球熱的風(fēng)潮，其中GPS（全球定位系統(tǒng)）與GPRS（通用分組無(wú)線業(yè)務(wù)）的完美結(jié)合更是被應(yīng)用在了各行各業(yè)中。其中GPS與GPRS的實(shí)際應(yīng)用在汽車方面表現(xiàn)最為顯著，所占的比重約占所有應(yīng)用50%左右。隨著電子信息技術(shù)在生活中的廣泛應(yīng)用，研究者也開(kāi)始探究其在家庭中的應(yīng)用[3]?！百F重物品防盜追蹤器”就是利用GPS和GSM短信模塊開(kāi)發(fā)的一款家庭無(wú)線防盜應(yīng)用系統(tǒng)。在該系統(tǒng)中，當(dāng)發(fā)生盜竊情況時(shí)，罪犯的所在位置將在第一時(shí)間以具體的短信形式實(shí)時(shí)地發(fā)送到指定的手機(jī)中。整個(gè)裝置由主動(dòng)式紅外傳感器進(jìn)行檢測(cè)，檢測(cè)結(jié)果發(fā)送“異常自動(dòng)”反饋信息，完全變被動(dòng)為主動(dòng)，全部自動(dòng)化的操作，使家庭防盜不再盲目，使警方破案不再被動(dòng)。

在“貴重物品防盜追蹤器”中運(yùn)用GSM模塊，是因?yàn)檫@個(gè)信號(hào)覆蓋范圍廣，定位準(zhǔn)確，商業(yè)應(yīng)用廣泛。當(dāng)犯罪分子把“貴重物品防盜追蹤器”當(dāng)成真正的貴重物品帶走時(shí)，追蹤器里的通訊模版會(huì)發(fā)送意外信號(hào)給相應(yīng)的安全手機(jī)，發(fā)送形式為短信不間斷發(fā)送。為了讓這個(gè)時(shí)候的“貴重物品防盜追蹤器”開(kāi)始工作，設(shè)計(jì)了安全板，其作用是平時(shí)關(guān)掉“發(fā)射機(jī)”的電源，關(guān)鍵時(shí)刻讓“發(fā)射機(jī)”發(fā)揮作用。當(dāng)“發(fā)射機(jī)”脫離“安全板”一分鐘后會(huì)即刻撥打“報(bào)警電話”，同時(shí)，“電子地圖”上將會(huì)顯示罪犯的地理位置信息[4]。

1.1 系統(tǒng)組成

系統(tǒng)主要由單片機(jī)控制機(jī)構(gòu)、GSM模塊、GPS模塊、無(wú)線發(fā)送器、磁場(chǎng)傳感器、備用電源組成。

作為系統(tǒng)中最主要的部分——移動(dòng)通信模塊和單片機(jī)，采用的分別是德國(guó)西門子的TC35通訊模塊和AT89S52系列單片機(jī)。其中德國(guó)西門子的TC35通訊模塊自帶RS232通訊接口，實(shí)現(xiàn)了與單片機(jī)及PC機(jī)的直接連機(jī)通訊，使短消息能迅速并且安全傳輸。作為保障短信報(bào)警能正常實(shí)現(xiàn)的移動(dòng)通訊模塊，基帶處理是其核心，主要負(fù)責(zé)處理傳輸?shù)紾SM終端內(nèi)的數(shù)據(jù)信號(hào)，并覆蓋了蜂窩射頻器中的所有模擬和數(shù)字功能。在沒(méi)有額外硬件電路的情況下，可支持HR（半速率編碼譯碼器）、FR（全速率編碼譯碼器）和EFR（增強(qiáng)型全速率編碼譯碼器）語(yǔ)音信道編碼。TC35通訊模塊的外圍電路由IGT（Ignition）啟動(dòng)電路、SYNC（Synchronization）指示燈電路、SIM（Subscriber Identification Module）卡電路及串行接口電路組成。

1.2 工作原理

系統(tǒng)中的短信收發(fā)部分由單片機(jī)控制、數(shù)據(jù)接收和發(fā)送、終端處理三個(gè)模塊組成。單片機(jī)是系統(tǒng)的控制中心，為了增強(qiáng)系統(tǒng)的性能，采用的單片機(jī)是低耗高能的AT89S52單片機(jī)。在TC35通訊模塊接收到信息之后，單片機(jī)便將數(shù)據(jù)從內(nèi)存中讀出，隨后借助GSM網(wǎng)絡(luò)將數(shù)據(jù)發(fā)送出去。單片機(jī)的內(nèi)存相當(dāng)于數(shù)據(jù)的中轉(zhuǎn)站，控制著數(shù)據(jù)的接收與發(fā)送。所有被接收的數(shù)據(jù)代碼便進(jìn)入到終端處理部分的模塊，被進(jìn)行一定的處理后，最終被儲(chǔ)存至數(shù)據(jù)庫(kù)中，之后會(huì)被用來(lái)后期操作的讀取和查詢[5]。其中，為了確保系統(tǒng)工作性能的穩(wěn)定，這里不惜減少工作的效率，保守選擇采用半雙工模式的單片機(jī)與通訊模塊通信方式，即任何時(shí)刻只允許一方發(fā)送數(shù)據(jù)或接收數(shù)據(jù)。

系統(tǒng)采用具有特制芯片的GS-89M-J作為GPS模塊，具有高效節(jié)能的特點(diǎn)。GS-89M-J最鮮明的特點(diǎn)是芯片不但體積小，還內(nèi)建了ARM7TDMI CPU可快速定位追蹤32顆衛(wèi)星，并且內(nèi)建了200，000個(gè)衛(wèi)星追蹤運(yùn)算器，具有高效率的搜尋和運(yùn)算衛(wèi)星訊號(hào)的能力，與此同時(shí)還有定時(shí)定位功能。

最終的“貴重物品防盜追蹤器”主程序流程如圖2所示。

2 出警線路優(yōu)化算法

在“貴重物品防盜追蹤器”的技術(shù)支持下，其物品所在的具體位置將通過(guò)GSM網(wǎng)絡(luò)（TC35）模塊以短消息形式實(shí)時(shí)準(zhǔn)確地發(fā)送到指定手機(jī)。在這樣的基礎(chǔ)上，警方怎樣根據(jù)罪犯所在地及周邊的警員情況，智能生成最優(yōu)的出警線路，以便最快到達(dá)目的抓捕罪犯成為下一步研究的方向。最優(yōu)路徑（即最短路徑）問(wèn)題是路線設(shè)計(jì)及分析等優(yōu)化問(wèn)題的基礎(chǔ)，是交通、物流等網(wǎng)絡(luò)分析的核心內(nèi)容之一[6]。如何選擇到達(dá)報(bào)警位置的時(shí)間最短路徑，其基本思想也是最短路徑的優(yōu)化求解。在不同領(lǐng)域不同的環(huán)境中，最短路徑問(wèn)題有許多種類的算法和實(shí)現(xiàn)方式。針對(duì)道路環(huán)境較為穩(wěn)定的情況，可以應(yīng)用靜態(tài)的路徑優(yōu)化算法，如Dijkstra算法，以及BFS（最好優(yōu)先算法）算法、Floyd算法、盲目搜索等。在不同的具體問(wèn)題中，由于路網(wǎng)環(huán)境有所不同，采用不同的路徑搜索方法的效果便可能存在很大的不同[7]。

作為最經(jīng)典的最短路徑搜索算法——Dijkstra算法，雖然簡(jiǎn)單易用并總能搜索到最短路徑，但是Dijkstra算法有個(gè)硬傷，即當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較多的時(shí)候，它的效率是非常低的，因?yàn)樗枰阉魅康墓?jié)點(diǎn)。而對(duì)于出警線路而言，時(shí)間就是破案的關(guān)鍵，耗費(fèi)的運(yùn)算時(shí)間較大，不能滿足出警的實(shí)際需求[5]。因此Har，Nilsson提出的A*算法就脫穎而出。

A*算法（或稱A-Star算法）是啟發(fā)式搜索算法之一，能在靜態(tài)路網(wǎng)中最有效的找出最短路徑。它是在充分考慮了Dijkstra算法和BFS（最好優(yōu)先搜索）算法的優(yōu)缺點(diǎn)后總結(jié)建立的路徑算法。盡管遍歷搜索法的思路還是能在它的整體框架上看出來(lái)，但是對(duì)于地圖上任意一點(diǎn)到目標(biāo)點(diǎn)的時(shí)間估算上它采用了啟發(fā)函數(shù)。這樣的啟發(fā)式搜索會(huì)優(yōu)先搜索那些具有特定信息的節(jié)點(diǎn)，選擇可能性最大的節(jié)點(diǎn)作為下一個(gè)搜索節(jié)點(diǎn)，提高了搜索效率。A*算法在具體的搜索過(guò)程中，會(huì)根據(jù)系統(tǒng)中已有的數(shù)據(jù)，對(duì)待搜索的節(jié)點(diǎn)到目的地的距離進(jìn)行評(píng)估，再進(jìn)行進(jìn)一步的搜索[8]。

其中，g（n）（深度因子）是從起點(diǎn)到當(dāng)前節(jié)點(diǎn)n的實(shí)際時(shí)間估計(jì)值，h*（n）（啟發(fā)因子）是從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最短路徑的時(shí)間估計(jì)值。這里h*（n）不能等于0，因?yàn)槿绻鹔*（n）=0，也就是說(shuō)沒(méi)有利用任何全局信息，不滿足A*算法的條件。h*（n）的選取對(duì)于A*算法至關(guān)重要。只有滿足不能高于節(jié)點(diǎn)n到終點(diǎn)的實(shí)際最短距離的相容性條件，才可以得出出警的最優(yōu)路徑。那么，如果滿足相容性條件，則原問(wèn)題必然存在最優(yōu)解，也就是說(shuō)，利用A*算法一定能夠求出出警的最短路徑。由此可知利用啟發(fā)函數(shù)的A*算法更加智能化，使搜索方向變窄、搜索深度變小，也使得搜索的節(jié)點(diǎn)數(shù)變少了，故占用的存儲(chǔ)空間也就少了，問(wèn)題的可行性也就增加了。

采用不同的啟發(fā)函數(shù)實(shí)際上是代表了不同的尋優(yōu)策略，因而針對(duì)不同的具體問(wèn)題也會(huì)出現(xiàn)不同的效果。

路徑搜索問(wèn)題本質(zhì)上是在網(wǎng)絡(luò)圖中尋找特定節(jié)點(diǎn)之間代價(jià)最小的行進(jìn)路徑[9]。作為啟發(fā)式搜索算法代表的A*算法，具有其一系列特點(diǎn)。通過(guò)設(shè)置啟發(fā)函數(shù)，能夠從備選點(diǎn)中選擇具有最小代價(jià)值的點(diǎn)作為優(yōu)先的后繼節(jié)點(diǎn)，因而避免了大范圍的搜索過(guò)程，減少搜索的成本，特別是對(duì)于數(shù)據(jù)規(guī)模比較大的地圖，其效率提升是非常明顯的。啟發(fā)式算法的目標(biāo)性比較強(qiáng)，其對(duì)路徑的選擇也可能由于過(guò)于依賴啟發(fā)算子導(dǎo)致丟失最優(yōu)解。通過(guò)不斷改進(jìn)算法的啟發(fā)函數(shù)，可以基本達(dá)到滿意的求解結(jié)果。

3 結(jié)束語(yǔ)

本文針對(duì)貴重物品防盜問(wèn)題設(shè)計(jì)的基于GSM網(wǎng)絡(luò)的貴重物品防盜追蹤器，能夠有效確保物品失竊時(shí)可以向失主發(fā)送報(bào)警信息，還可以通過(guò)適當(dāng)改造而用來(lái)尋找、定位那些自制能力較差的兒童或患有智障/老年癡呆等疾病的成人，亦可使用在汽車、摩托車等大型貴重物品上。在貴重物品防盜追蹤器研發(fā)的基礎(chǔ)上，A*啟發(fā)式算法盡管在結(jié)果上有不足之處，但其處理速度相較于Dijkstra算法更加高效。Dijkstra搜索算法的運(yùn)算結(jié)果是全局最優(yōu)的，但是隨著地圖數(shù)據(jù)量的提高，資源耗費(fèi)過(guò)大，時(shí)間較慢。而時(shí)間消耗對(duì)于處理緊急事件的公安來(lái)說(shuō)的是至關(guān)重要的，因此應(yīng)采用與A*類似的改進(jìn)啟發(fā)式算法作為路徑優(yōu)化的相關(guān)模塊，使其與全局最優(yōu)的結(jié)果能夠更加接近。

本研究仍存在一些不足，比如防盜探測(cè)器的探測(cè)靈敏度問(wèn)題，在某些特殊場(chǎng)合的信號(hào)受到屏蔽和吸收的狀況，通信成功率降低的問(wèn)題等。

隨著GIS、GPS、GSM等技術(shù)的發(fā)展與進(jìn)步，為出警線路優(yōu)化提供了可能，也為維持良好的治安狀況起到作用。

參考文獻(xiàn)：

[1] 高俊紅.101出警線路優(yōu)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D].電子科技大學(xué)碩士

學(xué)位論文，2010.

[2] 張虎，施一民.基于MapX的公安110報(bào)警系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].測(cè)繪

通報(bào)，2004.9：23-39

[3] 裴蓓，趙麗.基于GSM的家庭遠(yuǎn)程智能監(jiān)控系統(tǒng)設(shè)計(jì)[J].制造業(yè)自動(dòng)

化，2013.9（35）：26-28

[4] DEREKENARIS G，GAROFALAKIS J，MAKRIS C，et al.Integrating

GIS， GPS and GSM technologies for the effective management of ambulances[J].2001（3）：267?278

[5] 張任，高雙，郭曉燕.基于GSM模塊的防盜監(jiān)控器設(shè)計(jì)[J].現(xiàn)代電子技

術(shù)，2013.15：27-28

[6] 尚華艷.物流配送中車輛路徑問(wèn)題研究[D].武漢理工大學(xué)碩士學(xué)位論

文，2005.

[7] 王正彬，杜文.考慮線路安排的物流配送方案模型及其算法研究[J].

物流技術(shù)，2003.12：72-73

[8] 鄒亮，徐建閩，朱玲湘.A*算法改進(jìn)及其在動(dòng)態(tài)最短路徑問(wèn)題中的應(yīng)

用[J].深圳大學(xué)學(xué)報(bào)理工版，2007.1：32-36

[9] 宋延，石建軍，許國(guó)華.適用于路徑規(guī)劃系統(tǒng)的動(dòng)態(tài)路網(wǎng)描述模型[J].

交通與計(jì)算機(jī)，2004.5（22）：28-31