一种预约式智能停车场及其LEACH路由算法改进

古　辉，顾杰杰

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)



一种预约式智能停车场及其LEACH路由算法改进

古辉，顾杰杰

(浙江工业大学 计算机科学与技术学院，浙江 杭州 310023)

摘要：通过超声波传感器实现对停车位上车辆有无检测，利用手机App来实时查询和预约停车位以及在线支付功能，提出了一种以超声波传感技术和无线传感网络技术，以及移动互联网络技术相结合的预约式智能停车场的控制与管理技术方案.在构建停车场无线传感网络过程中，基于某个特定的场景，提出了基于LEACH的簇树网络的路由算法改进方法，Matlab模拟实验表明，改进后的算法对节点能耗有很大减少，延长了停车场无线传感网络的生命周期，从而实现整个预约式智能停车场系统的有效管理.

关键词：停车位控制器；超声波；App；无线传感器网络；LEACH蔟树网络

随着我国车辆保有量的激增，开车堵和停车难问题在城市显得尤为明显，造成当前停车问题主要有以下5点：1) 停车位资源匮乏；2) 违章停放现象普遍；3) 停车设施利用率低；4) 管理存在盲点；5) 停车管理的信息化程度低.无线传感网络的兴起带动了停车场智能管理的发展，国内外研究日渐成熟，但能耗问题一直都是研究热点.Jong-Myoung Ki等[1]提出了一种无线传感器网络中基于模糊逻辑的簇头选举机制，通过使用模糊逻辑，收集和计算开销可以减少，并且传感器网络的寿命可以延长.Guang-yao Ji等[2]提出了一种上下文自适应聚类的高效的无线传感器网络数据融合方法，对改善能耗和网络寿命有很大成效.周玉等[3]提出了一种基于遗传算法的新型路由算法LEACH-GEC，较LEACH协议分簇更均匀，簇首选取更合理，有效延长了网络寿命.吴臻等[4]基于对能量和簇头间距的考虑，对LEACH路由算法的改进，提高了网络生存时间和簇负载平衡程度.

在上述研究的基础上，笔者提出一种预约式智能停车场，利用手机App进行预约，超声波传感器检测车辆有无，在线计时扣费，其中停车场中各个停车位传感控制模块构成了无线传感网络，基于以上文献都是在无线传感网络大范围下提出的改进或者新算法，没能针对停车场进行特定环境进行深度处理，提出一种更加适合停车场场景的LEACH的簇树网络的路由算法改进方法，在节点能耗方面得到很大改进，使得整个预约式智能停车场系统能够完成停车到收费的自动化管理.

1系统概述和流程

1.1系统概述

基于无线传感网络的预约式智能停车场主要组成：具有查询和预约车位以及在线支付功能的手机App[5-6]，是由具有无线通信和温湿度检测的Telosb节点、超声波传感器以及车位锁等组成的停车位控制模块.系统结构框图如图1所示.图1中的Sink, EndDevice只是分工不同的Telosb节点[7].

图1　预约式智能停车场系统框架图Fig.1　The frame chart of reserved-intelligent parking lot system

Sink节点一方面负责收集各个EndDevice的车位信息并通过串口输出到电脑终端存储到后台中心，另一方面转发后台指令到某个具体的EndDevice实现车位锁的操作.EndDevice实现车辆的检测和对车位锁的操作.

1.2系统流程

预约式智能停车场的系统停车流程如图2所示，可分为如下6个步骤：

1) 车主打开手机App，输入停车地点、时间和搜索范围，搜索可用车位：范围内无有可用车位，返回1)；搜到可用车位，进入2).

2) 根据距离依次显示最佳车位，用户决定是否进行预约：不预约，返回2)；选择某个车位进行预约，进入3).

3) 系统锁定车主预约的车位，对后台数据库的车位状态进行更新，提供用户到达该车位的导航功能.

4) 车主到达该车位后，点击手机App的开锁按钮，通过后台传送开锁指令到具体的车位锁，实现开锁，车辆驶入，停车计费开始.

5) 超声波传感器模块开始工作，对车辆是否离开进行检测：检测到未离开，返回5)；检测到离开，进入到6).

6) 自动产生停车费用，从手机App的用户账户上扣除，并自动对车位上锁，后台更新车位状态.

图2　系统停车流程图Fig.2　The flowchart of Parking system

2停车位检测控制模块

2.1Telosb节点

采用美国美新半导体(MEMSIC)公司开发的telosb节点TPR2420CA作为控制器和无线通信模块，TPR2420CA把所有要素都集中在一个独立的平台上：USB 编程能力，IEE802.15.4 射频器和天线，低功耗扩大内存得MCU和可选的传感器套件，其内部结构如图3所示.

图3　Telosb节点内部结构Fig.3　The internal structure of Telosb Node

2.2超声波传感器模块

笔者采用HC-SR04超声波测距模块，具有测距精准和性能稳定等优点，模块包含超声波发射器、接收器与控制电路[8].该模块通过一个控制端口发送一个大于10 μs的高电平，接收端口等待高电平输出，一检测到就打开定时器开始计时，直到转为低电平时结束，通过高电平持续时间来计算测量的距离，公式为

测量距离=(高电平持续时间×声速)/2

式中声速为340 m/s.由于一般车辆底盘高度小于30 cm，只要对车辆的底盘高度进行检测，就能知道车位上是否有车辆存在.超声波传感器装在车位锁底盘上，底盘与地面距离为10 cm左右，这里设定测量阈值为20 cm.为达到测量的结果准确性，可通过以下步骤：

Step 1连续3次测量车位上车辆底盘与超声波传感器之间的距离：若3次测量值都有效且都小于设定的阈值20 cm，则判定车位上有车辆存在；若3次测量值出现至少一次未检测到有效值或者测量值大于阈值20 cm，则跳转Step 2.

Step 2再次测量车辆底盘与超声波传感器之间的距离：若测量值都有效且小于设定的阈值20 cm，则跳转Step 1继续测量；若未检测到有效值或者测量值大于阈值20 cm，则判定车位上无车辆存在.

通过实验发现，该策略能保证检测结果的成功率.在20 cm的阈值范围内，最低的判定成功率为95.5%.当要检测车辆离开的动作时，按照上面提到的检测车辆存在的策略，若上一次进行检测，判定结果为存在车辆，紧接着下一次测量结果判定为不存在车辆，则判定检测到车辆驶离的动作，从而正确做出相应的关闭车位锁的动作.

3LEACH蔟树网络的路由算法改进

3.1改进算法的簇树网络建立

假定一个拥有116 个车位的城市停车场，各个停车位上都配置一个车位锁，车位锁包括一个超声波传感器和一个无线传感网络通信模块，一个城市停车场无线传感网络就可以组建完成.网络只拥有一个Sink节点，Sink节点和计算机连接，所以不考虑能源问题，其主要负责汇聚和分发数据.这里防止安全干扰，对网络节点进行安全加密处理.为了设计简单，每一个车位的长度设为6 m，宽度设为3 m.国家技术监督局、建设部联合发布的《城市道路交通规划设计规范》中对机动车公共停车场出入口设计作了如下规定：少于50 个停车位的停车场，可设计一个出入口，其宽度宜采用双车道；50～300 个停车位的停车场，应设两个出入口[9].因此采用双出口，图4表示对应的城市停车场车位示意图.

将每个停车位抽象为一个无线传感器节点，就可以形成如图5所示的节点抽象图，每个节点的坐标值可计算得知.对车位进行编号，车位号n从1～116，并以各个车位的中心点作为节点的坐标.各节点的直角坐标值(xn,yn)与车位号n的关系式分别为

图4　停车场示意图Fig.4　The schematic diagram of the parking lot

(1)

(2)

式中：xn，yn分别为节点的横坐标和纵坐标；n为车位号.

图5　停车位节点抽象图Fig.5　The abstract diagram of Parking lot Node

在图5所示的停车场中建立簇树无线传感网络，可先将整个停车场区域划分为8个区，区内拥有一个簇头节点与多个子节点，该网络的汇聚节点Sink在停车场入口处，其坐标值(x0,y0)为(66,0)，Sink节点不算作116个车位节点.两个无线传感网络节点的有效通信距离设定为60 m，超过60 m就只能通过路由器转发才能到达.停车场的车位分区规划如表1所示.

表1　停车场车位分区表

表2　16位通信地址结构

LEACH协议采用了“轮数”的概念[10]，第一轮分为簇建立和稳定工作两个阶段，通常为了减少能耗，簇建立阶段的时间远小于稳定阶段的持续时间.LEACH协议在初始化阶段选取簇首按照以下策略来进行：

传感器节点随机生成一个0～1之间的随机数，并且与阈值T(n)做比较，选取小于该阈值的节点作为簇头.其中阈值T(n)的计算公式为

(3)

式中：p为节点成为网络中簇头节点的百分数；r为当前的轮数；G为一个集合，该集合中的节点是前1/p轮中没有充当过簇头节点的节点.

簇头节点选定之后，会向其他各节点广播自己成为簇头的消息，各节点根据收到消息的强度来选择加入哪个簇头，并告知该簇头节点.在稳定工作阶段，各个成员节点会将采集到的数据转发到簇头节点，经过数据融合之后，统一发送到Sink节点，一段时间后，进行下一轮循环[11].从中可以看出:LEACH协议是假定所有节点拥有相同的能量并且簇头节点能耗相同，在停车场网络节点能量不均衡的网络中不太适用.同时可能出现簇头分布过于集中，从而导致网络分布不均.

算法改进是针对蔟树建立的和簇头选择过程中的，建立簇树网络利用上述的逻辑地址来进行，其步骤如下：

Step 1选取各个区内的地址编码最小的节点作为簇头节点，选择bit8作为簇头标志位，并设置为1，默认状态为0，申请加入由Sink组建的网络.

Step 2计算区内的簇头节点与Sink节点的距离计算公式为

(4)

1)计算簇头节点与Sink节点之间的距离满足d(0,n)<60 m，则判定可以直达，直接加入网络，跳转到Step 4.

2)计算簇头节点与Sink节点之间的距离满足d(0,n)≥60 m，则判定为加入网络失败，跳转Step 3.

Step 3网络中剩余的未能加入无线网络的簇头节点通过搜索成功加入网络的簇头，并计算与各个簇头节点之间的距离d，满足d(0,n)<60 m情况下，取d最小的簇头节点作为父节点加入网络.若加入失败，则继续执行Step 3；若加入成功，则跳转到Step 4.

Step 4每个分区内的剩余节点依次加入到该分区的簇头节点下面，就此无线网络建立完成.

一轮完毕后，A，C，F三个簇首由于和基站的距离超过60 m[8]，选取离他最近的簇首作为下一跳，所以通过建立多跳路由方式来和基站通信，避免直接通信所要花费更大的能耗.其他簇首和基站的距离少于60 m，直接和基站通信.

簇首形成及路由算法示意图如图6所示.当簇树网络完成建立后，会随着节点剩余能量值来进行网络重构，以维持网络的最大寿命.其具体的重构方式如下：每一轮中计算各个区中的簇首节点的剩余能量(通过测量剩余电压值)，若发现任意一个簇头节点的剩余电压值低于设定的阈值v(v初始值为90%的节点额定电压，随着轮数的增加而做出相应调整，现设定每经过一轮降低10%额定电压)，则进行簇头重新选取，区内的节点能量值(电压值)由该区的簇头节点来收集，选取每个区内节点能量值最大(电压值最高)作为新的簇头节点，加入网络参考上述步骤.原先每个区内的簇头节点都将以新的簇头作为父节点加入网络，各区内剩余的节点都将加入到新的簇头节点下.

图6　簇首形成及路由算法示意图Fig.6　The schematic diagram of first cluster routing algorithm

3.2与LEACH路由算法仿真结果比较

采用Matlab 2015a平台作为仿真工具，通过仿真实验比较改进后的LEACH算法和未改进的LEACH算法.在本次仿真中，根据设定的停车场的一个真实环境，共计116个节点和一个Sink节点，传感器节点坐标分布图如图7所示.

图7　传感器节点坐标分布图Fig.7　The distribution map of sensor nodes coordinate

系统中的存活节点数目直接影响无线传感网络的生命周期，从图8可以看出：未改进的LEACH算法出现第一个死亡节点大约在270 s，而改进后的LEACH算法出现第一个死亡节点的时间大约是370 s.在相同的时间内改进后的LEACH算法的网络系统存活的节点数目明显多于采用LEACH 算法的网络系统.这是因为改进后的LEACH算法通过增加节点位置信息，并人为地对区域划分，更有效的簇头选取方式，保证簇头的能量为分区内最大值，均衡了网络负载，结合单跳与多跳的方式实现簇头节点的通信，很大程度上减少了节点的能量消耗.

图8　节点存活数Fig.8　The number of survival Node

从基站单位时间内接收到的数据量，可以看出该网络的传输时延，以及网络通信流畅度.从图9可见采用改进后的算法网络中的基站接收到的数据量远远大于采用LEACH算法网络中的基站接收到的数据量.这是因为改进后的算法避免了簇头节点过早死亡而导致网络生命周期过早结束，循环利用网络中的能量，以达到最大利用率.

图9　基站接收数据数量Fig.9　The quantity of the data received by base station

能量消耗问题是无线传感网络中最关心的指标，图10表示改进的LEACH算法和未改进的LEACH算法的系统总能量消耗对比图，从图10中可以看出：采用改进后的算法，网络中的总能量消耗速度较常规LEACH 算法能量消耗比较缓慢，随着轮数的增加，效果更显著.

图10　总能量消耗Fig.10　The quantity of total energy consumption

4结论

提出的预约式智能停车场系统能够将移动互联网技术和无线传感网络技术结合，提高了停车管理的信息化程度和设施利用率，“一车一位”的方式一定程度上减少了乱停放现象，使管理更加清晰化，最重要的是促使了停车的过程更加高效和方便.基于停车场特定的环境，提出在停车场无线传感网络中LEACH协议的改进算法，经过仿真表明，改进的LEACH算法在能耗和能量使用效率上得到很大改进，并能够更好地均衡网络负载，使得预约式智能停车场能够更有效的管理和操作，已运用到实际工程中.

参考文献：

[1]KIM J M, PARK S H, HAN Y J, et al. CHEF: cluster head election mechanism using fuzzy logic in wireless sensor networks[C]//Advanced Communication Technology (ICACT). New York: IEEE,2008:654-659.

[2]JIN G, PARK M S. CAC: context adaptive clustering for efficient data aggregation in wireless sensor networks[J]. Networking technologies, services, and protocols; performance of computer and communication networks; mobile and wireless communications systems,2006(5):1132-1137.

[3]周玉，景博，杨洲.一种基于遗传算法的无线传感器网络LEACH路由协议的改进算法[J].计算机研究与发展，2010(S2)：175-179.

[4]吴臻，金心宇.无线传感器网络的LEACH算法的改进[J].传感技术学报，2006，19(1)：34-36.

[5]周晓，边裕挺，李杰.基于Android智能终端的WSN监控系统[J].浙江工业大学学报，2013，41(5)：558-561.

[6]MOREIRA N, VENDA M ,SILVA C , et al.Mobile application to monitor a WSN[C]//Information Systems and Technologies (CISTI). New York: IEEE Press,2011:1-6.

[7]陆欢佳，俞立，董齐芬，等.基于无线传感网的楼宇环境监测系统设计[J].浙江工业大学学报，2011，39(6)：683-687.

[8]李军，申俊泽.超声测距模块HC—SR04的超声波测距仪设计[J].单片机与嵌入式系统应用，2011，11(10)：77-78.

[9]中华人民共和国建设部.城市道路交通规划设计规范：GB 50220—1995[S].北京：中国计划出版社，1995.

[10]彭静，刘光祜，谢世欢.无线传感器网络路由协议研究现状与趋势[J].计算机应用研究，2007，24(2)：4-9.

[11]周晓，朱仁烽，赵锋，等.基于人工蜂群算法的无线传感器网络路由协议[J].浙江工业大学学报，2014，42(5)：577-580.

(责任编辑：陈石平)

A smart reservation-parking system and an improved LEACH cluster routing algorthm

GU Hui, GU Jiejie

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The ultrasonic sensors are used to detect the parking situation and the Apps installed in cell phone can be used to inquire and reserve parking service in this paper. A control and management method for the smart reservation-parking is proposed combining with ultrasonic sensor technology, wireless sensor network technology, as well as mobile Internet technology. During construction process of wireless sensor networks in the parking system, based on a particular scene, an improved routing algorithm based on LEACH cluster tree network approach is proposed. The simulation experiments on Matlab show that the improved algorithm greatly reduces the energy consumption of nodes and extends the wireless sensor network life cycle in the parking system. The entire smart reservation-parking system can be managed effectively.

Keywords:parking control; ultrasonic; App; wireless sensor networks; LEACH cluster tree network

收稿日期：2015-11-10

作者简介：古辉(1962—)，男，山西孝义人，教授，研究方向为模式识别与图形图像处理技术，E-mail：gh@zjut.edu.cn.

中图分类号：TP391

文献标志码：A

文章编号：1006-4303(2016)02-0134-06