无线传感器网络k度覆盖控制算法
邢萧飞1，谢冬青1，郑瑾2
(1. 广州大学 计算机科学与教育软件学院，广东 广州，510006；
2. 中南大学 信息科学与工程学院，湖南 长沙，410083)
摘 要：
题提出一种利用勒洛三角形几何特征进行目标区域覆盖度的判断方法，并在此基础上设计k度覆盖算法(Reuleaux triangle-based k-coverage algorithm, RTC)。该算法首先把每个传感器节点的感知圆划分成6个相等的勒洛三角形区域，依定理判断该区域是否达到用户对网络覆盖度的要求，然后调度相应节点进入活跃状态实现对目标区域的k度覆盖。实验结果表明：RTC算法在保证网络覆盖质量条件下能够有效地降低活跃节点的数量，提高网络能量利用效率，从而延长网络生存期。
关键词：
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2014)11-3832-08
k-coverage control algorithm for wireless sensor networks
XING Xiaofei1, XIE Dongqing1, ZHENG Jin2
(1. School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China;
(2. School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: A k-coverage decision approach was presented using the geometrical characteristics of Reuleaux triangle, and a Reuleaux triangle-based k-coverage control algorithm (RTC) was proposed based on the coverage decision theorem. By slicing the sensing range of sensor into six cross Reuleaux triangle with the same size, the RTC algorithm first judges whether the region is k-covered based on the user’s requirements on coverage degree, then schedules the appropriate sensors into the active state to achieve the k-coverage of network. The simulation results show that RTC algorithm decreases the total number of active sensors effectively, improves the energy efficiency of network and prolongs the network lifetime.
Key words: wireless sensor network; k-coverage; Reuleaux triangle; state scheduling
无线传感器网络是集信息采集、无线通信于一体新型网络，能够帮助用户远程收集物理世界信息并以多跳方式将此信息传递给用户，将物理世界与信息社会联系在一起。网络覆盖问题是无线传感器网络中的一个基本问题，它主要反映传感器节点在部署后如何对目标区域的有效监测，也是网络服务质量(QoS)的重要评价指标之一。与网络覆盖质量优劣相关的是节点的部署方式[1]。在自然环境恶劣等条件下无法通过人工方式来部署节点时，则需要借助如飞行器等工具来部署节点，此类方法称为随机性部署节点方式。由于在这种部署方式中节点位置预先不确定，这种方式往往需要部署更多数量的节点，才能保障网络的健壮性和容错性，但这也带来了节点覆盖度控制问题。同时，对一些重要的目标区域如图1所示的军事战场上对敌方坦克等目标的实时监测，为了获得更高的监测质量要求，需要对目标区域实行多重覆盖，这就是多重覆盖问题，简称为k度覆盖问题[2-4]。本文主要针对随机部署方式下的网络k度覆盖问题进行研究。由于节点制造成本与体积的限制，传感器节点通常使用能量有限的电池来提供能量来源。在实际部署节点时，由于目标区域较大，这需要部署节点的规模较大，节点分布范围较为广泛，部署的环境也比较复杂，导致通过更换传感器节点电池或充电等手段来补充能量非常困难或很难实现。这个问题可以转化为最大化网络生存期问题，现有文献提出的解决方法主要有2种：第1种是控制节点的密度[5]，它主要应用在网络初始规划阶段；第2种是节点状态调度[6-8]，这种方法是在不降低系统服务性能的条件下，通过轮流选择一部分节点作为活跃节点，而让其他节点进入到低功耗的睡眠状态，减少活跃节点的数量，达到提高网络中节点能量利用效率的目的。本文将以节点调度方法为基础，设计k度覆盖算法。
图1 WSN在军事战场监测应用示例
Fig. 1 A monitoring application of WSN in military battlefield
随机节点部署方式下的k度覆盖问题可分解为2个子问题：第1，在网络覆盖的范围内，如何确保目标区域的任意一个目标都至少处在1个传感器节点的监测范围内；第2，当用户对网络覆盖度要求提高时，如何调度或移动传感器节点实现对目标区域的多重覆盖。针对以上问题，本文作者首先提出一种利用勒洛三角形几何特征对目标区域覆盖度的判别方法，然后在此基础上提出基于勒洛三角形的k度覆盖算法(Reuleaux triangle-based k-coverage algorithm, RTC)，通过调度相应节点的状态达到网络覆盖质量的要求。本文的主要研究内容包括：1) 分析现有的目标覆盖模型，提出利用勒洛三角形的几何特征对目标区域覆盖度的判定方法及定理；2) 基于节点状态调度机制，设计了k度覆盖算法(RTC)，算法具有复杂度低、扩展性好的优点；3) 通过仿真实验，以活跃节点数量和网络生存期为评价指标，通过对比CCP[8]分析了所提RTC算法的性能。
1 相关工作
现有文献对随机部署节点的网络k度覆盖问题的研究主要是基于覆盖集理论和节点状态调度策略进行解决。基于节点覆盖集理论的解决思路是按照一定的策略选择一部分节点，在满足完全覆盖整个目标区域的条件下最小化节点集规模。Ammari等[9]以节点集工作“轮”方式来研究多重覆盖问题，通过理论推导得到实现网络k度覆盖的充分条件，提出了4个配置协议来解决，协议能够选出最小数量的节点集而实现k度覆盖监测区域；同时，为了保证网络的连通性，提供了节点通信半径应与感应半径保持的比例关系。本文作者在文献[9]工作的基础上，将网络的k度覆盖问题与节点调度和数据转发问题结合在一起研究，设计一个基于地位位置信息的数据转发协议，协议主要是依据节点感应和通信范围的不同而选择相应的节点，从而实现对监测区域的k度覆盖[3]。Ashouri等[6]将部署的节点划分成若干不相交的节点集，每个节点集都能够单独覆盖监测区域，利用布尔可满足性(SAT)理论找到最优节点集构造方法，最后将此方法扩展应用来求解k度覆盖。陆克中等[10]提出了一种基于贪婪法的最小覆盖集近似算法，在构造覆盖集的过程中，优先选择扩展面积最大的有效节点加入覆盖集，算法构造的覆盖集规模较小，但该算法并不是分布式的，不适合能量受限的传感器网络。
基于节点状态调度方法的解决思路是借助节点位置信息，选择合适的节点，并将其调度为活跃状态来覆盖目标区域。对k度覆盖研究经典的协议是覆盖配置协议CCP[7-8]，它是利用节点的局部位置信息对节点是否满足覆盖要求的职能合格性判断，职能合格者将转为活跃状态，而不合格者将转为睡眠状态。并依据Hall等学者的覆盖理论[12]，提出了一种利用VORONOI图几何特征来判断节点是否冗余的方法，它首先找到节点的覆盖圆周之间的交点，以及这些覆盖圆周与网络部署区域的边界的交点；然后计算这些交点是否位于节点的覆盖圆周范围内；如果这些交点都至少被一个覆盖圆盘覆盖，那么整个网络部署区域就被完全覆盖了。如果这些交点都至少被k个覆盖圆盘覆盖，那么整个网络部署区域则被节点k度覆盖。但是，节点只能合格性判断算法在判别节点是否冗余的复杂度达到了O(N3)。王换招等[12]将k度区域覆盖问题转化为目标区域内若干特殊点的k度覆盖计算问题，提出了1种以保证k度覆盖为目标的集中式节点调度策略，按照时间轮次，算法以分布式方式确定节点的状态。Bejerano针对监测区域“覆盖洞”的多重覆盖问题，在不依靠节点局部位置信息的条件下，提出了精确的k覆盖验证方案，方案能够实现对不同尺寸的覆盖洞的准确检测[4]。
2 问题描述及分析
2.1 网络模型
现假设网络具有以下特征：
1) 传感器节点以随机形式部署在目标区域。
2) 节点在部署后能够获取自身的位置信息，节点位置信息可借助于低功耗的GPS[13]或其他定位技术[14]获得。
3) 节点采用圆盘感知模型，即节点的感知范围是以其所在位置为圆心，半径为Rs的圆形封闭区域，Rs称为节点的感知半径，Rs由传感器的物理特性决定。
4) 节点的部署密度较高，其数量通常是节点最优部署情况下的2~3倍。
2.2 相关定义
为了表述规范，给出相关术语的正式定义。
定义1 覆盖：在二维平面上，目标区域内任意一点与节点的最小距离小于Rs，称目标区域被节点覆盖。
定义2 k度覆盖：在二维平面上，目标区域内任意一点同时被k个活跃节点所感知，称目标区域被节点k度覆盖。
定义3 网络生存期：从网络正常工作运行开始，直到存在某一个监测目标不能被任何部署的节点所监测覆盖，这个时间段称为网络生存期。
本文使用1种名为勒洛三角形(Reuleaux triangle)的几何图形的性质来判别目标区域的覆盖程度，它的正式定义如下：
定义4 勒洛三角形：以等边三角形3个顶点为圆心，以其边长为半径作圆，所形成的3个圆周的交集区域，称为勒洛三角形。其形状为如图2所示的灰色区域。
根据定义可知：勒洛三角形是1个固定宽度的曲线图，以1个等边三角形为基础。勒洛三角形内任意1点到其边的距离均不大于其内接等边三角形的边长，边上的每个点到对应顶点的距离都是相等的。
图2 勒洛三角形
Fig. 2 Reuleaux triangle
2.3 网络k度覆盖条件及定理
为了更加直观有效地判断部署的节点对目标区域的覆盖程度，本文使用勒洛三角形的几何特征进行覆盖程度判定。其主要实现思想是在网络初始化完成后，利用Helly定理[15]来判断目标是否被节点k度覆盖。
定理1 Helly定理：假定X1, X2, …, Xn是Rd的1个有限子集合，这里n＞d，假如这个n个子集合中任意d+1个子集的交集不为空，那么，这个集合有1个非空交集；即
。Rd表示d维实数集。
图3 Helly定理在二维平面的一个应用示例
Fig. 3 A demonstration of Helly theorem in 2-D plane
根据定理1，在k≥3的条件下，当且仅当这k个几何图形中的任意3个的交集不为空时，这k个几何图形所形成的交集是1个非空集合。图3所示为Helly定理在二维平面上的1个示例，它表示在n=5，d=3条件下各个几何图形相交所形成的公共交集(区域)情况。由勒洛三角形的几何性质和定理1，可以得到如下判断目标区域或目标是否被节点k度覆盖的充分条件。
引理1：在k≥3的条件下，假如在一个勒洛三角形区域内存在k个处于活跃状态的节点，则该勒洛三角形区域被节点k度覆盖。
证明：根据勒洛三角形的几何定义，在勒洛三角形内的任意1点到其外面的勒洛三角形边的距离都不大于该勒洛三角形的边长，而节点具有相同的感知半径，如果在该勒洛三角形内存在k个处于活跃状态的节点，则这k个节点中的任一个节点到该勒洛三角形边的距离都不大于节点的感知半径，即该勒洛三角形被节点k度覆盖。因此，引理1结论成立，证毕。
在实际以随机形式部署节点的条件下，把节点部署区域划分成若干相邻的勒洛三角形而对目标的覆盖度判断是比较困难的，因此，本文采用下面的方法解决，首先将1个节点的感应圆周划分成6个相等的扇形区域，如图4(a)所示。每个扇形包含1个由连接2条边与扇形圆弧的交点所成的弦与该2条边所形成的等边三角形，在每个等边三角形上构造出对应的勒洛三角形，这样任意2个相邻的勒洛三角形的交集形成1个双圆弧区域，如图4(b)所示。然后，针对此双圆弧区域进行判断节点对区域的覆盖情况。
图4 2个相邻勒洛三角形所成的双弧形区域
Fig. 4 A 2-arch area formed by two adjacent Reuleaux triangles
引理2：在k≥3的条件下，如果在具有相同公共底边的2个勒洛三角形所形成的双弧形区域内存在k个活跃节点，那么，这2个相邻的勒洛三角形区域被节点k度覆盖。
证明：该双弧形区域是这2个勒洛三角形的公共区域，由引理1 知，双弧形内任意一点距离这2个勒洛三角形边上的任意1点都不大于其边长，而这2个勒洛三角形是相等的，因此，如果在双弧形区域内存在k个活跃节点，那么这2个勒洛三角形都能被这k个节点覆盖。证毕。
根据引理1和引理2，下面给出判断1个区域是否被节点k度覆盖的充分条件。
定理2：在k≥3的条件下，对于一个目标区域，如果在其内的任意一个勒洛三角形与其邻接的勒洛三角形所形成的双弧形区域内存在k个活跃节点，且勒洛三角形直线边长与节点的感知半径相等，那么这个区域被节点k度覆盖。
证明：假定该区域被划分成若干大小相等且相邻的等边三角形，其边长与节点的感应半径大小相等，如果由这些等边三角形所构造的勒洛三角形及其相邻的勒洛三角形所形成的双弧形区域内存在k个活跃节点，由引理2知，这2个勒洛三角形所在区域被节点k度覆盖。同理，如果其他双弧形区域都存在k个活跃节点，那么这些双弧形所在的2个勒洛三角形也被节点k度覆盖，因此，结论成立。证毕。
为了确定节点之间的连通性，下面给出定理3，它反映了保证网络覆盖的条件下，实现网络节点之间相互通信连通，节点通信半径与感应半径应该满足的约束条件。
定理3：在1个目标区域被节点完全覆盖的条件下，如果传感器节点的通信半径Rc与其感应半径Rs的比值满足Rc/Rs≥
，那么可确保目标区域中的传感器节点之间是相互连通的。
证明：要实现传感器节点之间能够相互通信，在保证节点完全覆盖目标区域的条件下，只需要节点的通信半径大于或等于相邻节点之间距离最小值集合中的最大值。如图5所示，节点a, b和c的感应圆周相交于o点，abc构造成1个等边三角形，ao之间距离等于节点感应半径Rs，相邻节点之间距离是节点的感应半径值的倍。而由于此种情况是相邻节点之间最小距离最大化的情况，因此，传感器节点的通信半径Rc与其感应半径Rs的比值满足Rc/Rs≥即可确保完全覆盖区域中的节点之间是相互连通的。证毕。
图5 二维平面上节点最优覆盖示例
Fig. 5 Demonstration for the optimal coverage in 2-D plane
由定理3得知：只要节点的通信半径与感应半径满足这个比例关系，即可以确保网络节点之间的连通性；也为覆盖算法的设计提供了连通性保证。
3 基于勒洛三角形的多重覆盖算法
由于传感器网络是一种能量受限型网络，为了提高网络能量利用效率，本文设计了一种基于勒洛三角形的覆盖算法RTC。本节首先介绍节点状态调度策略；其次给出RTC算法的主要实现思想和执行步骤；最后给出算法伪代码描述和其性能分析。
3.1 节点状态调度策略
3.1.1 节点状态调度思想
网络的运行时间按时间“轮”划分，每个时间轮又分为2个阶段：状态决定阶段和工作阶段。在每个时间“轮”的开始时刻，节点被唤醒进入准备状态。处于准备状态的节点根据其在一段退避时间内竞争活跃节点成功与否来决定自己下一个状态，若成功，则进入活跃状态；否则，则进入等待状态。当所有节点都进入了活跃或睡眠状态之后，节点状态决定结束。然后网络进入工作阶段，在此阶段中节点维持自己状态不变，直到本次时间“轮”结束。
在每一个时间“轮”开始时，全部节点都以一个概率p选举自己作为活跃节点，若竞争成功，则节点进入活跃状态，通过运行RTC算法调度周围的节点进入相应状态，满足网络覆盖度要求。
3.1.2 状态转换过程
节点工作在下面4种状态之一：准备(ready)、等待(waiting)、活跃(active)和睡眠(sleeping)。节点不同状态之间的转换过程如图6所示。
图6 节点不同状态转换关系图
Fig. 6 Node state transition diagram
准备状态：在每一个时间“轮”开始时，节点处于准备状态。然后节点以一个概率p选举自己作为活跃节点，若选举成功，则节点进入活跃状态，否则转入等待状态。
等待状态：竞争失败的节点转入等待状态，当其在初始时间段内成功接收到邻居节点发送的On-duty(工作)消息后，更新其他节点在本地保存的状态信息，然后进入活跃状态监测目标区域。
活跃状态：在节点竞争启动时成功的节点进入活跃状态，通过运行RTC算法判断其感知区域处于活跃状态的节点是否满足覆盖要求，若不满足，则发送On-duty消息调度处于等待状态的节点进入活跃状态，满足网络覆盖度要求。
睡眠状态：传感器节点关闭不必要的模块，节省能量消耗。在1个时间“轮”结束后，节点转为准备状态。
3.2 算法思想和实现步骤
节点以随机方式部署到目标区域后，在初始状态下，随机选择一部分节点处于活跃状态，其余节点处于等待状态；处于活跃状态的节点运行RTC算法。算法首先将每个节点的感应圆周划分成6个大小相等的扇形，然后每2个相邻的扇形构造出1个双弧形区域。根据定理2，节点依次判断其感知圆周内相间的3个双弧形区域是否被节点k度覆盖，并根据这些节点的剩余能量大小，优先将位于这个双弧形区域内的剩余能量高的节点转入活跃状态，以实现k度覆盖该节点的感应区域。
根据上面所介绍的RTC算法的思想，其主要实现步骤如下所述。
第1步：在每个时间“轮”的状态决定阶段开始时，节点处于准备状态。然后节点以1个概率p选举自己作为活跃节点，若选举成功，则进入活跃状态，否则转入等待状态。
第2步：处于活跃状态节点Si将其感知圆周划分为6个大小相等的扇形区域，并为每个扇形构造1个勒洛三角形，然后每2个相邻的勒洛三角形的交集区域构造一个双弧形区域，这样节点感知圆共划分成6个双弧形区域(lens[0, …, 5])，如图4(a)所示。
第3步：根据定理2，依次对节点相间的3个双弧形区域进行覆盖度判断，它包含3种情况：
1) 如果双弧形区域内处于活跃状态的节点数量大于k-1个，说明则该区域覆盖度大于要求的覆盖度，则节点Si发送Off-duty消息，依据剩余能量将剩余能量小、处于活跃状态的冗余节点转入睡眠状态；然后转到第5步；
2) 如果双弧形区域内处于活跃状态的节点数量小于k-1个，说明则该区域未达到k度覆盖要求，转到第4步。
3) 如果双弧形区域内处于活跃状态的节点数量为k-1个，说明则该区域达到k度覆盖要求，转到第5步；
第4步：节点Si向没有达到k度覆盖要求的双弧形区域内处于等待状态的节点，依据其剩余能量和需要转入活跃状态的节点数量发送On-duty消息，节点收到该消息后转入活跃状态。
第5步：在状态决定阶段结束时，若处于准备状态的节点没有任何状态调度消息，则其自动转入睡眠状态。
3.3 算法伪代码描述
RTC()
Input: 活跃节点集合S={s0, s1,…, sm}，状态决定阶段退避时间tm，覆盖度k；
Output: 节点调度为稳定的状态(活跃和睡眠);
1. { CL ← NULL; /*Initial phase*/
2. i, j,k ← 0;
3. While ( i <= N)
4. { 
;/*成员节点计算其感知单元对目标的覆盖映射*/
5. }/*end while* /
6. While ( tw > 0) /*簇头节点收集成员节点发送的mCOVER消息*/
7. { If (簇头节点收到mCOVER消息)
8. { CL[j].data ←mCOVER; /* 簇头节点存储收到的消息 */
9. j++;
10. }
11. }/*end while*/
12. Sort(CL[j].data); /*依据Ei和βi将CL由高到低排序*/
13. While ( j < i) /*簇头构造最优覆盖集*/
14. { If (Ej >= Ethr)
15. { 簇头发送mNOTICE消息到成员节点;
16. 成员节点调度相应的感应单元去覆盖目标;
17. }/*end if*/
18. k ← j;
19. While (k < i) /*删除重复覆盖记录*/
20. { If (CL[k].data包含在CL[j].data内)
21. {将重复覆盖信息CL[k].data从CL中删除;
22. }/*end if*/
23. j++;
24. }/*end while*/
25. j++;
26. }/*end while*/
27. }
网络在初始化后，依次将每个处于活跃状态的节点感应圆划分成6个相等的扇形，时间复杂度为O(n)，对每个节点的双弧形区域的覆盖判断处理循环次数为M次，所有节点的迭代次数为M×n，而M为常数。因此，提出的RTC算法时间复杂度为O(n)。
4 实验评估与分析
为了评价本文所提RTC算法的性能，本节使用C++设计了实验程序，并将RTC算法与CCP算法[6]在不同评价标准下的性能进行对比。
4.1 实验参数与评价标准
在实验中，传感器节点被随机部署在的400 m×400 m目标区域，节点能耗采用文献[16]所提出的能耗模型，其能耗分别设置为：ET-elec=50 nJ/bit，ER-elec=100 nJ/bit，εfs=10 pJ/(bit·m2)；其他实验环境参数设置如表1所示。
实验分别从不同的网络规模和目标区域覆盖度环境下，通过对比活跃节点数量和网络剩余能量评价RTC算法的性能，并对比不同的节点初始选举概率p值对网络覆盖度的影响。
表1 实验参数值
Table 1 Simulation parameters
4.2 实验结果与分析
4.2.1 活跃节点数量对比
图7所示为不同网络覆盖度下活跃节点数量对比关系。从图7可以看到：随着网络覆盖度的提高，网络中活跃节点数量明显增加。通过与CCP算法比较，RTC算法调度处于活跃状态节点的数量要比CCP算法的少，活跃节点数量规模减少的比例近似为15%。在确保网络3度覆盖的条件下，2种算法下处于活跃状态的节点数量相差不大；但随着网络覆盖度的提高，2种算法下处于活跃状态的节点数量差距增大，这说明RTC算法在保证网络覆盖度的条件下，更能够有效地提高判断网络覆盖度的准确性，从而调度更少的传感器节点处于活跃状态。
图7 不同网络覆盖度下活跃节点数量对比
Fig. 7 Comparison of number of sensor in active under different coverage degrees
4.2.2 网络剩余能量对比
图8所示为覆盖度k=3和k=4条件下网络剩余能量随时间变化关系。从图8可以看到：运行中的网络总的剩余能量随着网络运行时间增加而减少；与CCP算法相比，RTC算法在确保网络度的要求消耗的能量更少，其主要原因是RTC算法在判别网络覆盖度计算开销较小。在整个网络运行期间，RTC算法的网络能量使用效率平均提高20%。
图8 网络剩余能量随时间变化对比
Fig. 8 Comparison of residual energy of network
4.2.3 p值节点对覆盖度影响
图9所示为节点状态决定阶段开始时，设置不同的节点初始选举概率p对实现网络多重覆盖成功率的影响。从图9可以看到：随着p的增加，部署的节点能够达到所要求覆盖度的成功率也增加，但增加的速度较慢，其原因是网络中处于等待状态的节点数量较大。同时，通过对比不同p曲线，可以发现在节点密度较低时(节点数小于800)，选择p为0.3较合适；而在节点密度较高时，选择p为0.2较合适，该实验结果可用于指导用户在初始阶段对p的设置。
图9 p对覆盖成功率的影响(k=3)
Fig. 9 Comparison of coverage success ratio with different p
5 结论
1) 针对无线传感器网络的多重覆盖问题，提出了一个基于勒洛三角形的多重覆盖控制算法。
2) 该算法利用节点局部位置信息，通过在节点感应圆周上构造勒洛三角形进行判断网络的覆盖度情况，并根据网络节点的剩余能量和冗余情况进行节点状态调度，以提高节点能量利用效率。
3) RTC算法在确保网络覆盖质量的条件下能够有效地减少活跃节点的数量并提高网络能量利用效率，从而延长网络的生存期。
4) 本文所提算法在进一步的扩展后可以用于解决异构传感器网络的多重覆盖。
参考文献：
[1] Akyildiz I, Su W, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications magazine, 2002, 40(8): 102-114.
[2] 宁菲菲, 王国军, 邢萧飞. 无线传感器网络中一种基于节点序列的覆盖算法[J]. 中南大学学报(自然科学版), 2011, 42(7): 2028-2033.
NING Feifei, WANG Guojun, XING Xiaofei. Coverage algorithm with node sequences in wireless sensor networks[J]. Journal of Central South University (Science and Technology), 2011, 42(7): 2028-2033.
[3] Ammari H. CSI: An energy-aware cover-sense-inform framework for k-covered wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23(4): 651-658.
[4] Bejerano Y. Coverage verification without location information[J]. IEEE Transactions on Mobile Computing, 2012, 11(4): 631-643.
[5] Xing X, Wang G. Wu J, et al. Square region-based coverage and connectivity probability model in wireless sensor networks[C]// Proceedings of CollaborateCom. Washington D.C., 2009: 1-8.
[6] Ashouri M, Zali Z, Mousavi S, et al. New optimal solution to disjoint set k-coverage for lifetime extension in wireless sensor networks[J]. IET Wireless Sensor Systems, 2012, 2(1): 31-39.
[7] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration in wireless sensor networks[C]// Proceedings of SenSys. Los Angeles, CA, 2003: 28-39.
[8] Xing G, Wang X, Zhang Y, et al. Integrated coverage and connectivity configuration for energy conservation in sensor networks[J]. ACM Transactions on Sensor Networks, 2005, 1(1): 36-72.
[9] Ammari H, Das S. Centralized and clustered k-coverage protocols for wireless sensor networks[J]. IEEE Transactions on Computers, 2012, 61(1): 118-133.
[10] 陆克中, 孙宏元. 无线传感器网络最小覆盖集的贪婪近似算法[J]. 软件学报, 2010, 21(10): 2656-2665.
LU Kezhong, SUN Hongyuan. Greedy approximation algorithm of minimum cover set in wireless sensor networks[J]. Chinese Journal of Software, 2010, 21(10): 2656-2665.
[11] Hall P. Introduction to the theory of coverage processes[J]. Technometrics, 1998, 32(2): 237-238.
[12] 王换招, 董贝, 罗韩梅, 等. 基于k覆盖保证的异构传感器网络节点调度策略[J]. 西安交通大学学报, 2008, 42(8): 940-945.
WANG Huanzhao, DONG Bei, LUO Hanmei, et al. Node scheduling strategy based on k-coverage guarantee for heterogeneous wireless sensor networks[J]. Journal of Xi’an Jiaotong University, 2008, 42(8): 940-945.
[13] Buchli B, Sutton F, Beutel J. GPS-equipped wireless sensor network node for high-accuracy positioning applications[C]// Proceedings of EWSN 2012. Trento, Italy, LNCS 7158, 2012: 335-348.
[14] Zhou Z, Peng Z, Cui J, et al. Scalable localization with mobility prediction for underwater sensor networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(3): 335-348.
[15] Bollobas B. Intersecting convex sets: Helly’s theorem[M]. The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006: 90-91.
[16] Heinzelman W, Chandrakasan A, Balakrishnan H. An application specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.
(编辑 何运斌)
收稿日期：2013-12-15；修回日期：2014-03-15
基金项目(Foundation item)：国家自然科学基金资助项目(61272496)；NSFC-广东联合基金资助项目(U1135002)；中国博士后科学基金资助项目(2014M562153)；广州市教育局羊城学者基金资助项目(10A033D) (Project(61272496) supported by National Natural Science Foundation of China; Project(U1135002) supported by the NSFC-Guangdong Union Foundation of China; Project(2014M562153) supported by China Postdoctoral Science Foundation; Project(10A033D) supported by Yangcheng Scholars Foundation of Guangzhou Education Bureau)
通信作者：邢萧飞(1979-)，男，河南郸城人，博士，讲师，从事传感器网络研究；电话：020-39366925；E-mail: xxfcsu@gmail.com
摘要：针对网络覆盖问题提出一种利用勒洛三角形几何特征进行目标区域覆盖度的判断方法，并在此基础上设计k度覆盖算法(Reuleaux triangle-based k-coverage algorithm, RTC)。该算法首先把每个传感器节点的感知圆划分成6个相等的勒洛三角形区域，依定理判断该区域是否达到用户对网络覆盖度的要求，然后调度相应节点进入活跃状态实现对目标区域的k度覆盖。实验结果表明：RTC算法在保证网络覆盖质量条件下能够有效地降低活跃节点的数量，提高网络能量利用效率，从而延长网络生存期。
