摘 要:
虚拟扫描算法不能充分利用节点数量，为了延长网络生命周期它必须建立在节点密集部署的基础上，以致平均目标发现时间延长。为此，基于低占空比无线传感器网络（WSN），结合虚拟扫描波的思想，提出一种用于道路监测的多重虚拟扫描算法。该算法通过定点、同位置多节点部署的方式，使节点依次分批工作，以延长网络生命周期。仿真实验表明，多重虚拟扫描算法与虚拟扫描算法相比网络生命周期延长了180%，能有效提升网络性能。
多重虚拟扫描算法是一种用于道路监测的算法，它基于低占空比无线传感器网络，融入了虚拟扫描波的思想，并针对虚拟扫描算法不能充分利用节点数量方面优势的缺点，通过定点、同位置多节点部署的方式，使节点依次分批工作，大大延长了网络生命周期。仿真实验表明，多重虚拟扫描算法与虚拟扫描算法相比网络生命周期延长了180%，能有效提升网络性能。
关键词:
道路监测；虚拟扫描算法；定点；多节点部署；分批次
中图分类号: TP393.02 文献标志码:A
Abstract: VIrtual Scanning Algorithm（VISA) is unable to fully take advantage of the number of nodes, in order to prolong the network lifetime, it must be built on the basis of dense nodes deployment which makes the time for finding average target increase. Therefore, based on low dutycycle Wireless Sensor Network (WSN) by combining the ideology of virtual scan wave, the Multiple VIrtual Scan Algorithm (MVISA) was proposed for road surveillance. This algorithm adopted the way of fixing points, deploying the same location with multinodes to let the nodes to be worked in order and in batches, hence, the network lifetime could be greatly extended. Simulation result demonstrates that MVISA can prolong network lifetime by 180% when compared with VISA, improving the network performance effectively.
Key words: road monitoring; VIrtual Scanning Algorithm (VISA); fixed point; multinode deployment；batches
0 引言
无线传感器网络（Wireless Sensor Network,WSN）［1］由部署在监测区域内大量廉价微型传感器节点组成。它是通过无线通信方式形成的一种多跳自组织网络系统，对周围信息进行感知、采集，而后将数据进行处理回送给观察者。作为一项重要应用，基于无线传感器网络的道路监测也越来越受到重视［2-3］。
在道路监测应用中，节点能量使用的高效性和目标发现的及时性显得尤为重要。因此网络生命周期和平均目标发现时间成为了该应用的两项重要评估指标［4-5］。
目前道路监测相关的算法主要有持续苏醒(Always AwakeUp,AAU)算法、DC(DutyCycle)算法［6］和虚拟扫描算法（VIrtual Scanning Algorithm，VISA）［7-8］三种。AAU算法为非占空比网络，因此能量上不具有任何优势，在实际应用中局限较大。DC和VISA为低占空比网络，在能量控制上均有较好表现，在实际应用中有较强的适应性［9］。VISA通过对DC算法优化，融入了虚拟扫描的思想，与DC算法相比其网络生命周期延长了18.5倍。在目前无线传感器网络的道路监测中有广泛应用。但是VISA所延长的网络生命周期必须建立在节点密集部署的基础上，随之而来的问题则是平均目标发现时间延长。本文在研究和分析了VISA中存在的问题后，对其进行了改进并提出了多重虚拟扫描算法（MultiVIrtual Scanning Algorithm，MVISA）。在虚拟扫描的基础上，通过定点、同位置多节点部署的方式，使节点依次分批工作，从而进一步降低节点占空比，网络生命周期得到了较大提升。
1 VISA简介
1.1 网络模型
在长度为l的监测路段上，部署n个无线传感器节点。节点的检测半径为r（通信半径R与检测半径r不同，R>r）。入侵目标从入口（以下简称E点）向保护点（以下简称P点）运动。假设其最大速度为v，在目标到达P点前，网络必须发现目标［10］。
1.2 基本思想
VISA和DC算法的所有节点均以低占空比方式工作,即节点工作和休眠交替进行。与DC算法不同（其所有节点同时苏醒工作，并同时休眠），VISA的基本思想是让各节点按照从P点到E点的顺序依次苏醒，然后所有节点休眠一段时间后，再次让各节点从P点到E点依次苏醒。整个网络的工作过程类似一个从P点向E点的虚拟扫描波。当从E点向P点移动的入侵目标进入该虚拟扫描波的检测范围内时，目标将被网络发现（参见图1，图2）。
具体过程：网络在休眠Tsilent时间后，节点1苏醒并工作w时间后休眠，接着节点2苏醒并工作w时间后休眠，依此类推。当节点n工作w时间后，整个网络将休眠Tsilent时间，然后开始从节点1到n重新扫描（其中w为节点检测到目标的最短工作时间）。
要确保从E点运动到P点的目标能被准确发现，VISA的网络休眠时间Tsilent和节点休眠时间Tsleep分别为：
Tsilent=l/v
Tsleep=l/v+(n－1)w
因此VISA的网络生命周期Tnet和平均目标发现时间Tdetection分别为：
Tnet=Tlifewnw+lv
Tdetection=T1P1+T2P2=
l2v+l2(v+vnet)×P1+l2(v+vnet)×P2=
ll+nvw×l2v+l2(v+vnet)
其中：T1为网络休眠阶段平均目标发现时间，P1为网络休眠时间和网络周期的比值,即l/(l+nwv);T2为网络工作阶段平均目标发现时间，P2为网络工作时间和网络周期的比值，即nwv/(l+nwv);vnet为节点i到下一节点i+1的距离di,i+1与工作时间w之比，也可看做为虚拟扫描波的移动速度，即di,i+1/w。
1.3 VISA的缺点
由于非低占空比网络中的持续苏醒模式（AAU）在能量效率方面不具有任何优势。因此我们将比较对象设为DC算法和VISA。DC算法的网络生命周期Tnet为Tlifeww+lv。根据目标进入监测路段时网络的工作状态不同，其平均目标发现时间Tdetection可分为两种情况：1）网络处于休眠期，Tdetection为l/2v；2）网络处于工作期，Tdetection为0。而目标进入监测路段时网络处于休眠状态与一个网络周期的比例l/(wv+l)就必须考虑在内，因此DC的平均目标发现时间为l2/(2v(wv+l))。在VISA中其网络生命周期Tnet为Tlifewnw+lv。而平均目标发现时间Tdetection也需考虑两种情况即：1）网络处于休眠期，时间t∈(0,l/v)，Tdetection=l2v+l2(v+v网络)；2）网络处于工作期，时间t∈(l/v,(l/v)+nw)，Tdetection=l/2(v+vnet)。因此可以得出VISA整个网络周期内Tdetection=T1P1+T2P2。从表1可以看出，VISA的网络生命周期明显优于DC。但是DC的平均目标发现时间要比VISA短。从理论分析和仿真数据来看，VISA有两个主要缺点：1）未充分发挥其节点数量上的优势。VISA网络生命周期的延长与节点数目n成正比，也就是说VISA要发挥出其算法优势就必须大量密集部署节点，以增加节点休眠时间Tsleep。但是VISA并未充分发挥其节点数量上的优势，其网络生命周期还有上升空间。2）平均目标发现时间延长。由于两种算法网络机制的不同，DC算法的Tdetection要低于l/2v,而VISA算法的Tdetection要稍大于l/2v，这样VISA势必会降低系统发现目标的及时性。
假设某类型无线传感器节点的检测半径可达35m左右，那么该节点能检测大概70m距离的路段［11］。如果充分利用节点的检测半径来部署节点，那么网络生命周期将会有较大提升。
2 改进的MVISA
2.1 基本思想
MVISA也融入了虚拟扫描（VISA）的思想。与VISA节点随机密集部署的方式不同，MVISA的主要思想是按照定点、同位置多节点部署的方式，让相邻位置上节点的检测范围两两相切,每次只需少量的节点苏醒工作就能够确保目标被准确发现,而其余节点休眠，并按照预定的苏醒时间分批苏醒工作。网络整个工作过程类似于多个VISA网络持续地工作，进行多重虚拟扫描。
具体过程：根据节点的检测半径，按照一定规则部署好节点后，通过节点初始化完成所有节点苏醒时间的设置。第一批节点依次苏醒开始工作，其内部工作方式与VISA相同。当第一批节点能量耗尽后，第二批节点开始依次苏醒工作。待能量耗尽后由下一批节点依次分批苏醒进行工作。在此假设所有节点电池能量和功率相同。
2.2 节点部署
MVISA的节点部署采用定点、同位置多节点部署的方式，具体如下：
如图3所示，节点的数目为n(n=kl/(2r)，k为正整数）。节点按照图3的方式部署，每个部署点位之间相邻2r的距离，将n个节点部署在x（x=l/(2r))个位置上，每个位置部署k个节点(k也可作为节点批次数，即k批节点)。
要确保从E点运动到P点的目标能被准确发现，MVISA的网络休眠时间Tsilent和节点休眠时间Tsleep分别为：
Tsilent=l/v
Tsleep=l/v+(x－1)w
而MVISA的网络生命周期Tnet和平均目标发现时间Tdetection：
Tnet=kTlifewxw+lv
Tdetection=T1P1+T2P2=l2v+l2(v+vnet)×P1+l2(v+vnet)×P2=ll+xvw×l2v+l2(v+vnet)
其中:P1为网络休眠时间和网络周期的比值,即l/(l+xwv);P2为网络工作时间和网络周期的比值，即xwv/(l+xwv);x为节点部署位置数，也可作每批次工作节点的个数，即l/2r;vnet为节点i到下一节点i+1的距离2r与工作时间w之比，也可作虚拟扫描波的移动速度，即2r/w。
2.3 节点初始化
节点初始化的主要作用是设置各个节点的苏醒时间，具体步骤如下。
步骤1 由于k个节点均在同一位置，位于位置1的节点i以一个极小通信半径r0发出一个消息，周围k-1个节点均能收到消息，为并返回给节点i。节点i按照消息到达的顺序给每个节点设定苏醒时间并将消息返回。第s个到达的消息其消息发送节点的苏醒时间Tawake(s)为：
Tawake(s)=sTlifewxw+lv
各节点收到设置苏醒时间的消息后返回给节点i一个确认消息并等待，在节点i第一次开始工作时进行休眠。
步骤2 设定好位置1的k-1个节点的苏醒时间以后，节点i以通信半径2r进行通信。位置1的k-1个节点对此信息不做任何反应。在位置2的k个节点收到消息后均对节点i发出消息。节点i只对其接收到的第1条信息做出回复，指定其消息发送者节点j为下一跳节点，并设定其苏醒时间Tawake(j)为：
Tawake(j)=Tawake(i)+w
步骤3 节点j收到节点i的消息后，返回给节点i一个确认信息。按照步骤1对位置2周围的k-1个节点设置其苏醒时间，并按照步骤2指定下一跳节点k。
步骤4 节点k收到节点j的信息后，重复步骤3，直到位置x的节点。这时所有节点均完成了苏醒时间的设置。
步骤5 节点i开始工作，并通知位置1的k-1个节点休眠并开始计时以便在预定时间苏醒；而后节点j工作，并通知位置2的k-1个节点休眠；直到位置x的某个节点开始工作，通知位置x的k-1个节点进行休眠，完成整个网络的初始化。所有节点按照设定的苏醒时间开始依次分批工作。
3 仿真实验
以下是对MVISA进行仿真实验，仿真工具为Matlab,目的是验证基于MVISA道路监测网络性能的优劣。除非特别指出，本节所有实验都采用表2中的实验参数。
3.1 节点数目n对网络性能的影响
如图4所示，随着n的增大，VISA中节点休眠时间Tsleep增大，Tnet也呈线性增大。同样MVISA中由于n增大，节点批次数k也随之增大，Tnet也会增大。从曲线上分析，MVISA的生命周期增长的斜率要高于VISA，能较好地发挥出节点数量优势。而n对三种算法的Tdetection影响不大。DC要略优于VISA和MVISA，这是由于DC的工作机制是节点全部苏醒，而VISA、MVISA是节点依次苏醒。比如：当节点数目n为200时，MVISA与VISA相比Tnet延长了180%，与DC算法相比Tnet延长了12.7倍，而DC的Tdetection为24.5s，VISA、MVISA为25.725s。
3.2 节点工作时间w对网络性能的影响
如图5所示，三种算法均随着w的增加，节点的占空比增大，Tnet降低；而w对VISA、MVISA的Tdetection影响不大,而DC随着w从1到10，其Tdetection从24.5s缩短至20.8s。这是由于w增大，其网络工作时间与一个网络周期的比值wv/(wv+l)也增大，平均目标发现时间也就随之缩短。因此在MVISA中w应在可能范围内尽量取最小值，以提高网络生命周期。
3.3 节点检测半径r对网络性能的影响
如图6所示，随着r的增加，MVISA在监测路段上所需必要节点就越少。如果保持网络的节点数不变，MVISA的节点批次数k将增加，其Tnet也随之增大。而r对三种算法的Tdetection影响不大,DC要略优于VISA和MVISA。因此MVISA的r越大，其网络性能越好。比如：当r为32.5m时，MVISA相比VISA其Tnet提高了112.5%。
3.4 目标移动速度v对网络性能的影响
如图7所示，随着v的增加，网络休眠时间Tsilent和节点休眠时间Tsleep均减少，因此三种算法的Tnet也会随之缩短，而Tdetection则随之减少。图7显示出在所有速度情况下，MVISA的网络生命周期Tnet优于VISA、平均目标发现时间Tdetection与VISA相比变化不大。比如：在目标移动速度为5m/s时，MVISA的网络生命周期比VISA延长了120%。
以上反映了多种参数变化对三种算法的网络性能影响，MVISA与VISA、DC相比，其Tnet最长，其Tdetection优于VISA。
4 结语
WSN在道路监测中的应用越来越广，其节能算法研究也越来越受到重视。本文在节能算法VISA基础上，提出了MVISA算法。该算法采用定点、同位置多节点部署的方式，通过一次节点初始化设置好各个节点的苏醒时间，而后网络所有节点按照时间表分批次依次苏醒工作。理论分析和仿真实验表明MVISA的网络生命周期比DC和VISA算法有较大增加，其网络性能有显著提升。
参考文献:
［1］夏俐，陈曦，赵千川，等.无线传感器网络及其应用简介［J］.自动化博览，2004,21（1）：33-35.
［2］ 李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45（1）：1-15.
［3］尚德申，石建军.交通控制区域动态划分研究［J］.道路交通与安全,2007,7(1):27-29
［4］李颖宏，王力，尹怡欣.区域交通信号系统节点分析及优化策略研究［J］.计算机应用，2010，30（4）:1107-1109.
［5］ CARDEI M, THAI M T, LI Y,et al. Energyefficient target coverage in wireless sensor networks［C］// INFOCOM 2005: 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Washington, DC: IEEE Computer and Communications Societies, 2005, 3: 1976-1984.
［6］TIAN D, GEORGANAS N D. A node scheduling scheme for energy conservation in large wireless sensor networks［J］ . Wireless Communication and Mobile Computing,2003,3(2): 271-290.
［7］JEONG J, GU Y, HE T,et al. VISA: Virtual scanning algorithm for dynamic protection of road networks［C］// INFOCOM 2009: 28th Annual Joint Conference of the IEEE Computer and Communications Societies. Washington, DC: IEEE Computer and Communications Societies, 2009: 927-935.
［8］JEONG J, GU Y, HE T, et al. Virtual scanning algorithm for road network surveillance［J］. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(12): 1734-1749.
［9］HE T, KRISHNAMURTHY S, STANKOVIC J A, et al. Energeefficient surveillance system using wireless sensor networks［C］// MobiSys 04: Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services. New York: ACM, 2004: 270-283.
［10］ GUI C, MOHAPATRA P. Virtual patrol: A new power conservation design for surveillance using sensor networks［C］// IPSN 2005: Fourth International Symposium on Information Processing in Sensor Networks. Piscataway, NJ: IEEE, 2005: 246-253.
https://spirit.cs.ucdavis.edu/pubs/conf/ipsn05.pdf
［11］于宏毅,李鸥,张效义.无线传感器网络理论、技术与实现［M］.北京：国防工业出版社,2008:143.