摘 要： 高效的公安系统决定着社会治安的状况，为了能迅速定位犯罪分子并迅速出警，提出了“防盗追踪器”的设计思路。在比较各类路径优化算法的基础上，基于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等技术的发展与进步，为出警线路优化提供了可能，也为维持良好的治安状况起到作用。