基于防盜追蹤器的出警線路優化研究

徐瑩　林佳珍

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

關鍵詞： 防盜追蹤； GPS； 出警； 線路優化； A*算法

中圖分類號：TP277；TP301.6 文獻標志碼：A 文章編號：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 引言

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

1 貴重物品防盜追蹤器設計思路

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

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

1.1 系統組成

系統主要由單片機控制機構、GSM模塊、GPS模塊、無線發送器、磁場傳感器、備用電源組成。

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

1.2 工作原理

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

系統采用具有特制芯片的GS-89M-J作為GPS模塊，具有高效節能的特點。GS-89M-J最鮮明的特點是芯片不但體積小，還內建了ARM7TDMI CPU可快速定位追蹤32顆衛星，并且內建了200，000個衛星追蹤運算器，具有高效率的搜尋和運算衛星訊號的能力，與此同時還有定時定位功能。

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

2 出警線路優化算法

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

作為最經典的最短路徑搜索算法——Dijkstra算法，雖然簡單易用并總能搜索到最短路徑，但是Dijkstra算法有個硬傷，即當網絡中節點數較多的時候，它的效率是非常低的，因為它需要搜索全部的節點。而對于出警線路而言，時間就是破案的關鍵，耗費的運算時間較大，不能滿足出警的實際需求[5]。因此Har，Nilsson提出的A*算法就脫穎而出。

A*算法（或稱A-Star算法）是啟發式搜索算法之一，能在靜態路網中最有效的找出最短路徑。它是在充分考慮了Dijkstra算法和BFS（最好優先搜索）算法的優缺點后總結建立的路徑算法。盡管遍歷搜索法的思路還是能在它的整體框架上看出來，但是對于地圖上任意一點到目標點的時間估算上它采用了啟發函數。這樣的啟發式搜索會優先搜索那些具有特定信息的節點，選擇可能性最大的節點作為下一個搜索節點，提高了搜索效率。A*算法在具體的搜索過程中，會根據系統中已有的數據，對待搜索的節點到目的地的距離進行評估，再進行進一步的搜索[8]。

其中，g（n）（深度因子）是從起點到當前節點n的實際時間估計值，h*（n）（啟發因子）是從當前節點n到目標節點的最短路徑的時間估計值。這里h*（n）不能等于0，因為如果h*（n）=0，也就是說沒有利用任何全局信息，不滿足A*算法的條件。h*（n）的選取對于A*算法至關重要。只有滿足不能高于節點n到終點的實際最短距離的相容性條件，才可以得出出警的最優路徑。那么，如果滿足相容性條件，則原問題必然存在最優解，也就是說，利用A*算法一定能夠求出出警的最短路徑。由此可知利用啟發函數的A*算法更加智能化，使搜索方向變窄、搜索深度變小，也使得搜索的節點數變少了，故占用的存儲空間也就少了，問題的可行性也就增加了。

采用不同的啟發函數實際上是代表了不同的尋優策略，因而針對不同的具體問題也會出現不同的效果。

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

3 結束語

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

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

隨著GIS、GPS、GSM等技術的發展與進步，為出警線路優化提供了可能，也為維持良好的治安狀況起到作用。

參考文獻：

[1] 高俊紅.101出警線路優化系統的設計與實現[D].電子科技大學碩士

學位論文，2010.

[2] 張虎，施一民.基于MapX的公安110報警系統的設計與實現[J].測繪

通報，2004.9：23-39

[3] 裴蓓，趙麗.基于GSM的家庭遠程智能監控系統設計[J].制造業自動

化，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模塊的防盜監控器設計[J].現代電子技

術，2013.15：27-28

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

文，2005.

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

物流技術，2003.12：72-73

[8] 鄒亮，徐建閩，朱玲湘.A*算法改進及其在動態最短路徑問題中的應

用[J].深圳大學學報理工版，2007.1：32-36

[9] 宋延，石建軍，許國華.適用于路徑規劃系統的動態路網描述模型[J].

交通與計算機，2004.5（22）：28-31