梁 伟，陈燕飞，李 娜

（常熟理工学院计算机科学与工程学院 常熟215500）

1 引言

随着我国城市汽车保有量的不断攀升，城市交通问题日益突出。例如城市“停车难、乱停车”现象非常普遍，既影响城市功能的发挥，也给居民汽车消费造成障碍。而目前我国大型停车场仍不具备智能车位管理系统。对于用户而言，置身于大型停车场中，快速到达有效停车位仍相对困难，这样便造成停车场整体运行效率低，甚至会因为停车不方便造成管理混乱。因此，本文提出了停车场车位自动化检测的研究方案。该研究方案将运用到无线传感器的网络设计中，并利用无线传感器网络日益成熟的技术解决停车场自动化管理的难题。利用该方案能及时统计空闲车位，分配用户指定车位，加快用户的泊车速度，提高停车场的运行效率，并节约成本。

近年来，车辆传感器网络获得了研究界极大的研究兴趣。2010年，加拿大Ottawa大学PARADISE研究实验室在车辆传感器网络定位服务发现协议和辅助定位的网关广播发现协议中获得了多项研究成果；2011年，美国加州大学在车辆传感器网络信息传播合作的主动安全控制应用方面，也同样进行了相关的研究。国内方面，如上海交通大学在车辆传感器网络及新一代智能交通信息服务的研究中也颇有成果。

2 停车场传感器网络系统总体概述

大量的传感器节点被随机散布在目标监测区域；对网络进行网络拓扑规划；在数据收集过程中，需要每个传感器采集到的有效数据及时、准确地传回节点和基站；传感器节点采集大量的实时数据进行压缩处理。系统提供了停车场中总车位占用数以及更为具体的区域信息。在每个入口、出口和区域过渡处安放了传感器。入口和出口处的传感器，以无线方式将入口和出口的车辆数据传输到出口岗亭的中心基站，监测区域过渡点的传感器检测车流和方向，并确定车辆是否在区域间移动。传感器将数据发送到中心基站，基站将对所有的数据进行分析，实时提供停车场总共可用的停车位数量和每个区域的停车位数量。车位检测系统由4部分构成：

·安装在停车场车位上的车位检测器和安装于天花板的路由节点构成的自组织无线传感器网络；

·由无线射频模块和监控机组成的停车场网关服务器；

·由PC机组成的停车场管理终端，用于管理停车场的车位使用情况和监控设备运行状态；

·安装在停车场天花板下的LED显示屏，用于显示停车场剩余车位的显示情况，数据传输采用主动方式，传感网采集车位占用与否，数据无线发送给停车场网关服务器。

其中，车位检测器由微处理器、无线通信模块、电源模块、传感器模块构成。微处理器定时查询传感器模块状态。电源模块负责提供一个稳定的电压给微处理器，在适当的时候关闭一些模块，使整个系统进入低功耗状态。

处理器模块：采用低功耗单片机，因为采用电池供电，要求系统的平均电流要低，才能延长产品的使用寿命。

无线通信模块：射频芯片是标准的低成本、低功耗、单片、高集成度的解决方案，工作在免费频带上，主要特点为具有接扩频序列基带调制解调和有效数据传输速率；适合简化功能装置和全功能装置操作；电池电量可监控，适合各种恶劣的环境。

电源模块：实现节点设计的微型化，电池每月自放电率小于10%，在以网络形式工作状态下通过合理的配置节点发射极的接收、发射以及待机状态，可有效地延长节点的运用寿命。针对节点供电单元不便于更换的无线传感器网络，新的能源处理要领研究及网络系统的低功耗设计也是当前值得关注的课题。

传感器模块：射频芯片能对光、麦克风、震动做出传感，无线传感器网络节点的数据采集部分可以根据不同的应用采用不同的传感器，比如温度、湿度、光、压力、烟雾等。

3 通信与时间复杂度

车位检测的网关协议基本上分为3类：

·主动方式，网关在整个网络中广播自己；

·被动方式，请求车辆遍布于整个网络广播区域；

·混合方式，网关以固定的周期广播自己，请求车辆在广播区域内发送它们的请求消息。

主动方式具有很好的连通性，但是如果在网关数目很多的情况下，成本也会相应提高。被动方式对于小型的网络成本比较低，但可拓展性很差。混合方式相对于主动和被动方式有效得多，然而最重要的是怎样确定广播区域的半径。在本文中，笔者提出了一种新的混合自适应性的辅助定位网关广播和发现协议。这种机制不仅是混合式的，而且也是自适应性的，因为它可以根据变化的网关客户端数量和已经存在的网关数量来确定网关广播区域半径，以网关的分布方式和动态方式确定主动的广播区域。笔者对主动和被动网关发现进行比较，避开了混合协议的缺陷，并且调整了网关广播的半径。

3.1 主动广播区域

首先考虑网关G想发送广播消息给它的源车辆。网关G为网关广播确定了一个主动的广播区域，当一辆车V在主动广播区域中接收到了一个网关广播消息时，为了确认网关广播消息已经到达了源车辆，主动广播区域应该具有一个和其他区域一样的预期区域。为了保证V和G属于同一个主动广播区域，其他区域可以被添加进去(如图1所示)。这种算法提出了一个锥形的主动广播区域。如果考虑到预期区域是一个以(t1-t0)×v为半径的圆，那么提出的锥形的主动广播区域是能够获得的最小的区域。

然而，锥形的主动广播区域不是最佳的主动广播区域。如果所有从G到V的路径存在锥形的主动广播区域外的车辆，就不能够保证在锥形的主动广播区域中找到一条V和G的路径。因此，需要对广播区域拓展，可以采用一个矩形的主动广播区域(如图2所示)或者一个半圆形的主动广播区域(如图3所示)。如果请求车辆的搜索区域里存在网关，那么利用定位辅助广播和发现协议可以在有限的时间内找到请求车辆所请求的网关；如果一个请求车辆的周围有很多的网关，那么在一个有限的时间内请求者会收到所有网关的回复。

3.2 通信与时间复杂度的计算

在这一部分中，先确定主动广播区域，再计算通信和时间复杂度。

（1）计算锥形的主动广播区域面积

H0(x0,y0)是车辆V在t0时刻以速度v行驶的位置，G(xg,yg)是网关G的固定位置，t1是下一周期广播的起始时间。

图1显示了锥形的主动广播区域Rt△ADG的近似面积。如果确定了A、G和D的坐标，就可以确定△AGD的面积。G的固定坐标是xg和yg，A(xa,ya)和B(xb,yb)取决于A的预期区域。用以H0为圆心、以最大距离为半径的圆表示V的预期区域，这样就可以被车辆V在t1时刻以速度v穿过。因此，圆C可以用C(H0，(t1-t0))来表示。D在x轴上的投影可以确定D的横坐标为xd=x0+(t1-t0)×v，D在y轴上投影显示了yd和yg是相等的。所以D的坐标是(x0+(t1-t0)×v,yg)。A在x轴上投影显示了xa和xd是相等的。因此,xa=x0+(t1-t0)×v。A的纵坐标需要更多的计算。实际上，从图1注意到ya=y0(t1-t0)×v+d。可以使用三角函数计算出d的距离。在此之前，△BCG和△AEB是相似的。实际上，△BCG和△AEB分别是直角三角形。此外，∠GAD和∠BAE是相等的。因此，由于△AGD和△ABE相似，所以它们至少有两个角相等，所以，第三个角∠AGD和∠ABE也是相等的。另外，由于△BCG和△ADG有一个角相等并且是直角三角形，所以它们也是相似的。因此，可以得出△BGC和△ABE也是相似的。

现在应用直角三角形的三角函数：

最后，已知了△ADG所有顶点的坐标，可以很容易地知道△ADG的面积：

所以，锥形主动广播区域的面积为：

（2）计算矩形的主动广播区域的面积

H0(x0,y0)是车辆V在t0时刻以速度v行驶的位置，G(xg,yg)是网关G的固定位置，t1是下一周期广播的起始时间。

图2中显示了矩形的主动广播区域的矩形ABGD的面积。如果确定了A、B、G和D的坐标，就可以确定矩形ABGD的面积。G(xg,yg)的坐标是固定的。A(xa,ya)、B(xb,yb)和D(xd,yd)的坐标取决于车辆V的预期区域。用以H0为圆心、以最大距离为半径的圆表示V的预期区域，这样就可以被车辆V在时刻t1以速度v穿过。因此，圆C可以用C(H0，(t1-t0)×v)来表示。A、B和D在x轴和y轴上的投影可分别确定A、B和D的横坐标和纵坐标，分别为：A(x0+(t1-t0)×v,yg)、B(x0+(t1-t0)×v,y0+(t1-t0)×v)、D(xg,y0+(t1-t0)×v)。

在确定了矩形ABGD所有点的坐标后，可以简单地确定ABGD的面积：

所以，矩形主动广播区域的面积为：

（3）计算半圆的主动广播区域的面积

H0(x0,y0)是车辆V在t0时刻以速度v行驶的位置，G(xg,yg)是网关G的固定位置，t1是下一周期广播的起始时间。

图3显示了半圆的主动广播区域的面积是以G(xg,yg)为圆心、半径为R=GP的半圆。如果确定了G和P的坐标，就可以确定半圆SC的面积。G(xg,yg)的坐标是固定的。P(xp,yp)的坐标取决于车辆V的预期区域。如前文所述，用以H0为圆心、以最大距离为半径的圆表示V的预期区域，这样就可以被车辆V在t1时刻以速度v穿过。因此，圆C表示为C(H0，(t1-t0)×v)。P在x轴和y轴上的投影可确定P的横坐标和纵坐标，为P(x0+(t1-t0)×v,yg)。

现在，可以简单地确定半圆SC的面积：

所以半圆形主动广播区域的面积为：

（4）计算网关广播消息的数量

G(xg,yg)是网关G的坐标。H0(x0,y0)是车辆V在t0时刻以速度v行驶的位置，t1是下一周期广播的起始时间，ρ是车载网络的密度，nd是网关广播的频率。

在该网关发现协议中，网关广播消息的数量主要取决于主动广播区域。主动广播区域是可变的，它主要取决于车辆的预期区域和通过网关的请求区域。锥形的主动广播区域相对于矩形和半圆形的主动广播区域有更多的局限性。在另一方面，半圆的主动广播区域比锥形和矩形的主动广播区域面积要大。假设密度为ρ，在已知主动广播区域的密度后就可以确定主动广播区域中车辆的数量。

S1、S2、S3的计算分别得出了锥形、矩形和半圆形的主动广播区域的面积。在计算了主动广播区域的面积后，假设密度为ρ，就可以简单地确定主动广播区域中车辆的数量N：

为了避免消息的冗余，网关广播消息的传播在主动广播区域中是受控制的。因此，每一辆在主动广播区域中的车辆只转发第一次收到的广播消息，已经转发过的广播消息会被忽略。由此，在主动广播区域中的同一个消息只会被传播一次。所以：

其中，Na为广播消息的数量。

由于网关是定期传播广播消息的，把时间等分成每一小段△t，并且假设在考察的时间段内广播的数量为n，因此可以得到在一个周期内广播的数量np：

因此，在最坏的情况下，网关广播消息的数量取决于主动广播区域和广播的频率。相应的等式为：

其中，n1、n2、n3分别为锥形、矩形和半圆形主动广播区域的广播消息。

（5）计算请求消息的数量

V的坐标为(xv,yv)，网关G的坐标为(xg,yg)，车载网络的密度为ρ。

图4说明了一个服务请求者车辆的请求区域在主动区域之外的情况。在最坏的情况下，如果一辆车辆不在网关的主动广播区域中，想要找到一个网关，那么其请求消息将会一直被传播下去，直到有一个属于主动广播区域的网关接收到。假设消息的传播和车辆行驶的方向一致，则可以确定请求消息所在的区域。在本文的协议中，为了避免传播冗余的消息，请求消息的传播是受控的。也就是说，同一个消息只被车辆转发一次。所以，在请求消息传播的区域中，请求消息的数量和车辆的数量是相同的。

设车辆V的请求消息的数量为nq，则：

（6）计算回复消息的数量

在最坏的情况下，主动广播区域中的所有车辆排在一条线上，那么回复消息将会被主动广播区域中的所有车辆转发。

在这种情况下，一个网关的回复消息的数量为：

其中，S是相应的主动广播区域的面积，ρ是车载网络的密度。

结论1消息的复杂度是由网关的数量和请求车辆的数量决定的。网关的主动广播区域面积不是固定的，而是动态和自适应变化的。消息的复杂度取决于请求车辆的位置和运动状态，所有消息的复杂度是在考察的时间段内每一辆请求车辆的广播消息的数量、请求消息的数量和相应的回复消息的数量的总和。

被交换的消息的总数为：

结论2时间的复杂度是在考察的时间段内服务请求车辆收到第一个服务回复的平均时间。ns是请求车辆发起网关发现的数目。在最坏的情况下，网关请求车辆发出的网关请求消息会一直被传播，直到找到一个网关接收。然后网关必须生成一个回复消息并且回复给请求者车辆。因此，假设请求者发给网关的请求消息的数量为nq，网关回复给请求者的消息的数量nr，λt是消息在车辆传感器网络中传播所需的时间。因此请求车辆收到它的第一个回复消息的时间为：

因此，一个网关请求车辆收到第一个网关回复的平均时间为：

4 结束语

本文讨论了车载网络辅助定位在车位检测技术中的理论研究，并给出了停车场无线传感器网络设计的总体设计方案。在本文中，提出了一种新的混合自适应性的辅助定位网关广播和发现协议。这种机制不仅是混合式的，而且也是自适应性的，因为它可以根据变化的网关客户端数量和已经存在的网关数量确定网关广播区域半径。以网关的分布方式和动态方式确定主动的广播区域。对主动和被动网关发现进行比较，避开了混合协议的缺陷，并且调整了网关广播的半径。详细地给出了计算车辆传感器网络广播协议的消息交换的复杂度和消息传输总时间复杂度的公式。该设计方案在提高整个控制系统效率方面具有重要的作用，在未来的工作中，需要对该设计方案的性能进行评估，并且和已经存在的用于大型停车场的无线传感器网络设计方案进行比较，并将该方案运用于不同的设计模型中。

1 冯驰,刘希胜.基于ZigBee的无线环境监测网络设计.应用科技,2009,36(5):39～42,60

2 孟振飞,赵亚灵,侯贻帅.基于ZigBee技术的无线数传模块设计.电子元器件应用，2010,12(4):37～39,43

3 Boukerche A,Abrougui K,Pazzi R W.Context-aware and location-based service discovery protocol for vehicular networks.Proceedings of the 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc,Sensor,and Ubiquitous Networks,Spain,2009:93～100

4 昌学年,姚毅,闫玲.位移传感器的发展及研究.计量与测试技术,2009,36(9):42～44

5 Morgan Y L.Notes on DSRC&WAVE standards suite:its architecture,design,and characteristics.IEEE Communications Surveys & Tutorials,2010,12(4):504～518

6 郭稳涛,何怡刚.基于RFID的智能停车场管理系统的研究与设计.自动化技术与应用,2010,29(6):61～64

7 Zhao Jijun,Li Hua,Zhao Xin.The comparative research on the location technology of wireless sensor networks.Communications and Network,2009,1(2):114～120

8 鲁资,林水生,周亮.基于无线传感器网络的温度场绘制.传感器与微系统,2011(30):17～19

9 Mak T K,Laberteaux K P,Sengupta R,et al.Multichannel medium access control for dedicated short-range communications.IEEE Transactions on Vehicular Technology,2009,58(1):349～366

10 Huang C L,Guan X,Fallah Y P,et al.Robustness evaluation of decentralized self-information dissemination control algorithms for VANET tracking applications.Proceedings of IEEE 70th Vehicular Technology Conference，VTC2009-fall,Alaska,USA,2009

11 Jiao J B,Ye Q X,Huang Q M.A configurable method for multi-style license plate recognition.Pattern Recognition,2009,42(3):358～369

12 Kavitha T,Sridharan D.Security vulnerabilities in wireless sensor networks:a survey.Journal of Information Assurance and Security,2010(5):31～44

13 Padmavathi G,Shanmugapriya D.A survey of attacks,security mechanisms and challenges in wireless sensor networks.International Journal of Computer Science and Information Security,2009,4(1&2)

14 Bi Yuanguo,Liu Kuanghao,Cai L X,et al.A multi-channel token ring protocol for QoS provisioning in inter-vehicle communications.IEEE Transactions on Wireless Communications,2009,8(11):5 621～5 631

15 IEEE 802.11p-2010.IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-PartⅡ:Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications Amendment 6:Wireless Access in Vehicular Environments,2010