基于容忍覆盖区域的无线传感器网络节点调度算法
穆泉伶
摘 要： 无线智能小区中网络节点的有效能量覆盖控制是搭建智能化无线网络平台的核心问题。依托当前小区网络技术实际应用需求，对不同覆盖形式的典型算法进行分类描述。提出一种节点覆盖重叠最大有效覆盖率（OMEC）的控制覆盖算法，有效解决节点冗余、真空覆盖等问题。通过仿真实验模拟对比多种算法，结果表明该算法在提高网络覆盖质量以及延长网络服役周期等方面均有较明显的优势。
关键词： 智能化小区； 无线传感器网络； 覆盖控制； 重叠最大有效覆盖率
中图分类号： TN711?34 文献标识码： A 文章编号： 1004?373X（2017）09?0073?05
Abstract： The network nodes′ effective energy coverage control in wireless intelligent community is the core issue to build the intelligent wireless network platform. On the basis of the actual application requirements of the current community network technology， the typical algorithms with different coverage forms are classified and described. A control coverage algorithm based on overlay maximum effective coverage （OMEC） of node coverage is proposed to solve the problems of node redundancy and vacuum coverage. Multiple algorithms are compared with simulation experiments. The simulation results show that the proposed algorithm has obvious advantages in improvement of the quality of network coverage quality and extension of the network service cycle.
Keywords： intelligent community； wireless sensor network； coverage control； overlay maximum effective coverage
0 引 言
随着城市数字化建设进程的不断深入，城市小区智能化建设水平是城市智慧的最直接体现，其智能化程度直接决定了城市的智慧等级。采用无线传感技术搭建小区无线网络平台实现小区智能化管理，解决了有线网络布线严重浪费、受雷电干扰严重、信号损失过大等弊端。利用体积较小的无线传感器，以分配节点的形式组织搭建小区覆盖监测网络。被监测到的数据由传输链路通过节点发送到基站或者汇集节点，再传输到系统数据网络管理平台。平台将对数据进行感知、采集、分类、分析比对等操作完成基于普通用户和应用程序的访问及操作。
网络覆盖性和传输连通性作为与智能化小区无线传感器网络（Wireless Sensor Networks，WSN）关系密切并且核心的问题，其直接影响了网络节点的覆盖区域以及覆盖质量，决定了网络的生存周期。对于容量较大、配套设施完善的小区，无线传感器节点的密度必然要与之相匹配，节点数量不仅多而且密度大。导致网络冗余信息量大，堵塞通信链路，网络传输质量低下，网络扩展性能降低，网络服役周期缩短。另外，从传感器节点的角度，节点向汇聚节点提供的数据正确率降低，导致汇聚节点进行数据收集存在不确定性，与真实数据存在较大出入。覆盖控制决定了智能网络是否能够实现有效监控能力[1]节能方面的冗余控制，同时也是解决通信冲突以及过量信息冗余的另一个需要着重解决的问题[2]。
1 WSN中覆盖控制算法类别
1.1 NSS算法[3]
NSS（Node Self?Scheduling）算法可以归结为确定性覆盖中的区域覆盖以及节能覆盖范畴。算法的优势明显：较好地解决了“覆盖遗失”的问题，实现了网络范围的完全覆蓋。在正常工作状态下，传感器节点可以区分为Sleep（睡眠）和Active（活跃）两种典型的状态。算法使得节点在两种状态下轮流工作，整个工作周期通过节点状态转换和工作两个阶段组成。在Active状态下，每个节点第一步要向其有效覆盖距离之内的邻居节点发送包括节点ID以及所在位置的广播信息，判断是否有邻居节点可以完成自身的感知任务。接下来的过程分为两种情况：若有可以替代的节点，则替代节点返回给该节点一条信息，节点进入Sleep状态；否则，节点继续进行感知。当节点和都处于其邻居节点包含的覆盖范围之内，且和同时符合睡眠条件，这就出现了不能被监测的区域，即网络“覆盖遗失”，如图1所示。为了解决覆盖遗失的问题，每个节点都需要在等待“退避时间”后才能进行状态检验，当节点符合睡眠状态时，还要进一步等待一定时间实时监听邻居节点的状态。但是，算法也存在一定的缺陷：边界节点在节点状态转换过程中不能进入Sleep状态，这将导致边界节点的生命周期过短，加剧了网络能耗。
在无线传感器网络中，节点能效的高效利用对于网络生命周期起着决定性的影响。采用节点Sleep和Active两种状态相轮换的工作方式，进而达到节能高效的目的，同时亦可相对有效地延长网络生命周期。这就要求在满足一定网络覆盖率的前提下，最大化的对节点集进行轮换[4?8]。
1.2 OGDC算法[9]
OGDC（Optimal Geographical Density Control）算法研究在满足无线传感器网络的覆盖范围及保证网络通信连通性的前提下，节点数量最小化的解决方法。算法将网络工作过程划分为长度相同的时间段，每个时间段开始时，网络中节点都缺省为“监听”节点，在进行选择后，若干节点被确定为工作节点，根据激活节点的两种不同位置形式确定下一个被激活的节点。
形式一：对于已知位置的一个激活节点，其下一个较优的激活节点的位置应该大约在距离此激活节点的覆盖半径处；
形式二：对于已知位置的两个激活节点在此两个激活节点的连线中点处取垂线，以两个激活节点为圆心的覆盖范围的交点（并和垂线相交）为起始点在垂线上取距离为覆盖半径的点处就是第三个激活节点的较优位置。若在较优位置没有所需节点，则应该寻找确定距离较优位置最近的节点作为激活节点，如图2所示。
随机规避机制可以使得网络中节点均匀耗能，并且能较好地解决信道冲突问题。收到发布消息的节点，根据算法设定本身状态为“工作”或者是“睡眠”，且这一状态在整个当前时间段内保持不变，直到下一个时间段开始。
1.3 PEAS算法[10]
PEAS（Probing Environment and Adaptive Sleeping）算法中的节点一般处于睡眠、探测和工作三种状态。算法优势体现在：无需提前保存和获知邻居节点的位置信息、可以对冗余节点进行关闭，所以节能效果显著。节点初始缺省状态均为睡眠状态，睡眠时间由探测速率确定。节点苏醒之后以一定的功率在设定范围内广播探测消息。如有工作节点，则收到消息后返回一则回复消息，睡眠节点重新恢复到睡眠状态。若内无工作节点回复消息，则睡眠节点开始工作。对于工作节点，如果在一定时间段之内接收不到回复消息，则工作节点须一直保持工作状态，就会出现负载过量，致使其耗尽能量，提前死亡。
由于篇幅有限，仅选择以上三种比较常见的算法进行简要说明，但是目前的网络覆盖控制算法大多还是将研究的重点放在区域覆盖的完全性上面。在对工作节点的选择工程中存在能耗过大，信息传输部分丢失等弊端。在智能化小区网络系统建设过程中，考虑在满足实际应用需求的前提下，网络区域只要满足一定的有效覆盖率即可，并不需要网络区域的完全覆盖，所以，有必要面向自身需求开发适合的算法（OMEC），实现节能、高效、稳定、安全的应用目标。
2 针对最大有效覆盖率的节点控制覆盖算法
本文设计提出了针对节点覆盖重叠最大有效覆盖率的控制覆盖算法OMEC（Overlay Maximum Effective Coverage），结合智能小区的实际构建环境，能有效提高网络覆盖标准，保证信息传输准确，解决数据包的冲突问题，减少网络消耗，延长网络生存周期。
为了使讨论的问题具有普遍性，所有无线传感器节点均放置在指定边长的二维方形区域内。现假定网络环境为如下形式：每个节点的网络覆盖距离均远小于所设置的实际网络区域范围；所有节点在网络中地位相同，各节点之间互相独立；当所有节点均为工作状态时，节点覆盖区域可以满足实际设置网络的要求。即体现节点高密度、大规模的网络部署特点；具有网络中节点同构，即每个节点具有相等的感知半径和通信半径，且需要满足通信间距必须≥2倍感知间距；网络中所有节点都要保持时钟同步。
2.1 最大覆盖面积和有效覆盖面积率
2.2.2 冗余节点的冗余覆盖度
定理2 个隶属于某一个传感器节点的冗余节点的冗余覆盖度是（当传感器节点和它的邻居节点互相作为冗余节点时，传感器节点同它的邻居节点的感知面积比值叫做冗余覆盖度）：
算法在应用概率原理、通信链路原理等基础理论指导下寻求网络无线传感器的最大有效覆盖面积和较低的冗余覆盖率。结合节点建立冗余连通图，通过设定阈值判定节点的冗余度是否低于阈值标准。通过节点信息，在链表中按照高低保存节点能量，达到节省网络开销，降低能耗的目的。
3 仿真实验比对分析
为了验证本文提出算法的可行性和稳定性，应用C语言开发了一个仿真平台，以100 m×100 m为实验覆盖区域范围，对本文OMEC算法和文中提到的文献算法在不同类型节点数量、网络传输覆盖率、冗余节点数量以及算法的网络生命周期等方面做了仿真实验对比，实验结果较好地验证了本文算法的可靠性，具有较明显的优势。
仿真结果如图5～图8所示。图5显示， OMEC算法在参数作用下对应相同的传感器节点，需要的工作节点数量明显少于其他算法。因為NSS与PEAS算法皆是通过加大传感器节点数量的方式达到对被监测区域的最大有效覆盖。图6显示，网络覆盖率与传感器节点的数量成正比。OMEC算法通过参数有效动态调节被检测区域的覆盖率，所以在初期阶段的覆盖率就要高于其他算法。在节点数量为108时，OMEC算法实现了最大面积的有效覆盖，其他算法分别在节点数量为129和138时达到有效覆盖。在有效覆盖方面，比较OMEC与其他两种算法的覆盖率平均值，覆盖率提升了12.3%。
图7显示，所有算法的冗余节点数量和网络有效覆盖率皆成反比。图8中，最初OMEC与NSS算法的网络生命周期大致相同，但是随着传感器节点数量的加大，两种算法的网络生存周期都有了不同程度的延长。在传感器节点数量为90时，网络生命周期达到基本平稳的状态。OMEC与NSS算法相比较，平均网络生命周期上升15.6%。相较于NSS非线性连续不间断的覆盖方式监测目标节点，OMEC在能耗方面也有明显优势。
4 结 论
本文对智能化小区的无线传感器网络覆盖控制算法进行了深入、系统的研究。算法在满足最大有效覆盖率的前提下对节点控制覆盖进行了求解和验证，应用概率方法对冗余节点进行判断。采用模拟仿真平台对本文算法与文献算法在节点数量、覆盖率、生存周期对比等方面进行实验比对及分析，结果表明，本文提出的算法具有一定的可行性，而且存在较为明显的优势。
参考文献
[1] 李明，石为人.异构传感器网络成本最优节点部署机制[J].重庆大学学报，2012，35（2）：55?59.
[2] 谢洁锐，刘才兴，胡月明，等.无线传感器网络的部署[J].传感器与微系统，2007，26（1）：4?7.
[3] VELTRI G， HUANG Q， QU G， et al. Minimal and maximal exposure path algorithms for wireless embedded sensor networks [C]// Proceedings of the ACM International Conference on Embedded Networked Sensor System. New York： ACM， 2003： 40?50.
[4] LI X Y. Coverage in wireless and sensor networks [J]. IEEE transactions on computers， 2003， 52（6）： 753?763.
[5] CARLE J， GALLAIS A， SIMPLOT?RYI D. Preserving area coverage in wireless sensor networks using surface coverage relay dominating sets [C]// Proceedings of 2005 the 10th IEEE symposium on Computers and Communications. Cartagena： IEEE， 2005： 347?352.
[6] CARLE J， SIMPLOT?RYI D. Energy efficient area monitoring by sensor networks [J]. IEEE computer magazine， 2004， 37（2）： 40?46.
[7] ZHANG H H， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks [C]// Proceedings of 2004 NSF International Workshop on Theoretical and Algorithmic Aspect of Sensors， Ad Wireless and Peer?to?Peer Network. [S.l.]： NSF， 2004： 89?124.
[8] TIAN D. A node scheduling scheme for energy conservation in large wireless sensor networks [J]. Wireless communications and mobile computing， 2003， 3（2）： 271?290.
[9] YE F， ZHONG G M， LU S， et al. PEAS： a robust energy conserving protocol for long lived sensor network [C]// Proceedings of the 23rd International Conference on Distributed Computing Systems. Washington， DC.， IEEE， 2003： 28?37.
