WSNs中一种寻找最小工作节点集的覆盖算法

王爱民,刘永强,张 婧,刘衍珩

(1.吉林大学计算机科学与技术学院,吉林长春 130012; 2.吉林大学符号计算与知识工程教育部重点实验室,吉林长春 130012)

WSNs中一种寻找最小工作节点集的覆盖算法

王爱民1,2,刘永强1,张 婧1,刘衍珩1,2

(1.吉林大学计算机科学与技术学院,吉林长春 130012; 2.吉林大学符号计算与知识工程教育部重点实验室,吉林长春 130012)

针对现有覆盖算法存在的很多冗余节点,提出了寻找最小工作节点集的覆盖算法.该算法分为两个阶段:第1阶段运行已有的覆盖算法;第2阶段运行节点替换算法,它用更少的节点替换更多的工作节点,如此循环迭代使工作节点数不断减少.仿真实验表明,该算法比其他覆盖算法能获得更多的休眠节点,使工作节点数减少10%左右,从而延长了网络生命周期.

无线传感器网络;覆盖;睡眠调度算法;休眠顺序

传感器技术、微机电系统、现代网络和无线通信等技术的进步,推动了无线传感器网络的产生和发展.无线传感器网络能应用于军事国防、环境监测、医疗护理和危险区域远程控制等诸多领域[1-2],在大多数应用场景中节点都是随机部署的,这样会导致部署的节点数远大于所需的节点数,当这些节点都工作时,将会存在大量的冗余节点,如果不对这些节点进行休眠调度,不仅增加了整体能量的消耗,还增加了数据的冲突.为此,人们已经在这方面进行了大量的研究[3-12].文献[6]提出的算法把区域划分成方格,1个方格只有1个节点工作,该算法并没有考虑到网络覆盖的问题.文献[7]提出了满足覆盖的休眠调度的Ottawa算法,该算法通过扇形来计算邻居节点对1个节点的覆盖,由于只考虑了节点感知区域内的邻居节点,所以该算法并没有判断出所有的冗余节点.文献[8]改进了文献[7]提出的算法,对覆盖进行了更精确的计算.文献[9]提出了覆盖配置协议(Coverage Configuration Protocol,CCP)算法,该算法判断冗余节点的方法是通过判断节点感知区域内所有交点的覆盖度是否都大于K.该算法在部署节点较多时不会产生盲点.文献[10]提出的算法对周边界覆盖给出了充要条件,得出更精确的结果.文献[11]提出的算法,首先基于欧拉距离选出能全覆盖整个监测区域的节点集,然后选择离每个节点最近的K-1个节点来满足K覆盖.文献[12]提出了基于虚拟正方形网格的覆盖算法(Virtual Square Grid-based Coverage Algorithm,VSGCA),该算法把每个节点的感知区域划分成小方格,然后计算每个邻居节点对这些小方格的覆盖.该算法虽然在休眠节点数上没有文献[9]提出的算法好,但是它的复杂度比文献[9]提出的算法低很多.

1　网络模型和问题描述

1.1假设及定义

下面给出一些假设和定义.假设若干同构节点随机部署在L×W的区域A,节点的感知模型和通信模型都是圆形,且感知半径R与通信半径Rc满足Rc≥2R(这样在满足覆盖的同时也满足连通[9]).

定义1 部署在区域A中的节点集合称为节点集,即S={u1(x1,y1),u2(x2,y2),u3(x3,y3),…,uk(xk, yk),…}.

定义2 节点ui(xi,yi)的感知区域为点的集合,即D(ui)={p(x,y)∈A|(x-xi)2+(yyi)2≤R2}.

定义3 节点ui的邻居节点集,即N(ui)={uj∈S|(xj-xi)2+(yj-yi)2≤

定义4 假休眠状态节点指一个节点不执行监测任务,但是能接收和发送消息,预休眠状态和预工作状态是状态转换中的两个临时状态,表示准备休眠和工作的节点,它们都能接收和发送消息.预休眠状态是从工作状态转换过来的,而预工作状态是从假休眠状态转换过来的.

1.2问题描述

上文介绍的覆盖算法都能使大部分节点休眠,但是节点感知区域之间仍存在很多重叠区域,它们的平均覆盖度都大于等于2.观察其运行结果,有些点的覆盖度为1,有些点为2,有些点为3,甚至更大.有些区域1个节点就可以覆盖,但是它们却用了两个或者更多的节点覆盖,而且对相同的网络拓扑,每次运行生成的工作节点个数都不一样,且差距很大.

假设在监测区域中有一子区域如图1所示,子区域A1,传感器节点集S1(包括所有部署在区域边界的边界节点,部署在区域中心的传感器节点a,以及区域内其他两个传感器节点b和c).要满足子区域A1的全覆盖,有两种覆盖方案:①全部的边界节点及节点b和c;②全部的边界节点及节点a.第1种方案比第2种方案的工作节点个数多1.由此可知,工作节点个数与节点的休眠顺序有关.若a节点先休眠,则b和c不能休眠;若b或者c先休眠,则a节点不能休眠.当监测区域非常大,且部署节点非常多时,每次生成的工作节点个数都不一样,且差距很大.文中提出的覆盖算法解决了上述情况,使得每次运行结果一样,并且得到的工作节点个数也是最少的,工作节点个数能减少10%,且随着监测区域的扩大和部署节点的增多,工作节点的个数减少得会越多.文中算法运行于图1拓扑结构,得到的工作节点为所有的边界节点和节点a.

图1　节点部署图

图2　理想的节点部署图

2　与休眠顺序无关的覆盖算法

2.1讨 论

这里给出一种比较理想的节点部署情况.如图2所示.4个圆(半径为感知半径的大小为R)相交于一点,节点之间重叠的区域非常少,每个节点的覆盖范围可看做是一个正方形,边长为21/2R,这些节点的位置可表示为

定义5 若一个位置p(x,y)属于C集合,则称该点为最佳位置.

2.2算法描述

该算法由两个阶段组成,第1阶段是运行已有的覆盖算法,获得工作节点集;第2阶段是对第1阶段获得的工作节点集进行优化处理,用更少的工作节点集替换它们.

2.2.1第1阶段

该阶段得到初始的工作节点集,可使用已提出的算法,由于CCP算法能得到较少的工作节点,故使用CCP作为第1阶段算法.在运行该算法时,所有应该休眠的节点都进入假休眠状态,在第2阶段这些节点就能发送消息,并且能接收其他节点发送的消息.这样当第1阶段结束时,所有的节点只有两种状态:工作状态或假休眠状态.

2.2.2第2阶段

第2阶段算法思想是先让一个假休眠节点ui为暂时的工作节点,然后计算有多少个工作节点可以休眠,若可以休眠的工作节点个数大于1,则让该假休眠节点成为工作节点,可以休眠的工作节点成为休眠节点.若可以休眠的工作节点个数等于1,且该假休眠节点ui比可以休眠的工作节点更接近最佳位置(定义5),则让该假休眠节点成为工作节点,可以休眠的工作节点成为休眠节点;否则,不让假休眠节点ui成为工作节点.

第2阶段的详细过程如下:

(1)开始时,为避免消息发送冲突,每个假休眠节点ui都等待一段随机时间;然后,发送测试消息,并修改自己的状态为预工作状态,同时设定一个定时器.

(2)工作节点收到该消息时,先判断自己是否已经收到其他假休眠节点发送的测试消息,如果收到,则抛弃该消息;否则,跳转到下一步.其他状态的节点接收到该消息都抛弃.

(3)保存发送节点ui的身份标识号码(IDentity,ID),在邻居状态表中把该邻居节点ui的状态改为预工作状态,然后运行CCP覆盖算法,若运行结果为非冗余节点,则不进行任何处理;若为冗余节点,则修改自己的状态为预休眠状态,并向节点ui发送预休眠消息,表示自己可以休眠,然后跳转到下一步.

(4)当一个预工作节点ui(即刚才发送测试消息的节点)收到预休眠消息时,首先判断该消息是否是发送给自己的,若是,则记录该预休眠消息;若不是,则抛弃.循环处理这一步直到节点的定时器超时,然后转到下一步.

(5)预工作节点ui计算接收到的预休眠消息的个数为n,若n≥2,则转步骤(6)处理;若n=1,设发送预休眠消息的节点为uj,则判断自己ui和节点uj哪一个更接近最佳位置(定义5表示的);若ui更接近,则转步骤(6)处理;否则,转步骤(7)处理;若n=0,则转步骤(7)处理.

(6)预工作节点ui向邻居节点广播确认消息,表示此次测试成功,修改自己的状态为工作状态,然后转到步骤(8).

(7)预工作节点ui向邻居节点广播取消消息,表示此次测试失败,把自己的状态修改回假休眠状态,然后转到步骤(8).

(8)当一个预休眠或工作节点收到确认消息时,首先判断发送该消息的节点ID是否是自己记录的节点ID,若不是,则不进行处理;若是,则判断自己的状态,若为工作状态,则不进行处理;若为预休眠状态,则修改自己的状态为假休眠状态,并告知邻居节点自己的状态.若一个预休眠或工作节点收到取消消息时,同样先判断发送该消息的节点是否是自己记录的节点,若不是,则不进行处理;若是,则判断自己的状态;若为工作状态,不进行处理;若为预休眠状态,则修改自己的状态为工作状态,并告知邻居节点自己的状态.

(9)至此,1次迭代过程完成,在一段时间后,则继续以上步骤迭代,如此循环,直到所指定的时间为止.最后把所有的假休眠节点的状态改为休眠状态,整个算法结束.

在步骤(3)中,如果两个邻居节点同时判断为冗余节点,并且让这两个节点休眠,则有可能产生盲点.因为每个节点在进行冗余判断时都假设对方是工作节点.为解决这个问题,需在步骤(3)引入回退机制.该回退机制与CCP算法的回退机制相同.

2.3状态转换

图3只列出了算法第2阶段出现的状态,第1阶段结束后节点只有两种状态:工作状态和假休眠状态.在第2阶段节点的状态有工作状态、假休眠状态、预工作状态、预休眠状态和休眠状态.当算法结束时,节点只有两种状态:工作状态和休眠状态.状态转换如图3所示.

图3　状态转换

2.4时间复杂度

文中算法是由两阶段组成的,第1阶段运行CCP算法,第2阶段运行节点替换算法.CCP算法的时间复杂度为O(n3)(n表示感知区域内的邻居节点数)[9].在第2阶段,对于工作节点,当它接收测试消息时,使用CCP算法判断自己是否为冗余节点,由于此时网络中的平均覆盖度为一个常数,与初始部署节点数无关.所以,在节点的感知半径不变的情况下,工作节点的邻居工作节点数也为常数,因此,1次冗余判断的时间复杂度为O(1).又由于它有n个邻居节点,需要判断n次,故工作节点在第2阶段的时间复杂度为O(n),而假休眠节点在第2阶段只是对接收信息的判断及变量的设置,所以它的时间复杂度为O(n),故文中算法的时间复杂度为O(n3)).

3　实验结果及分析

这里使用仿真实验实现提出的无线传感网寻找最小工作节点集(Finding the Minimum working sets in Wireless Sensor networks,FMWS)算法,并与其他算法(Ottawa算法、CCP算法和VSGCA算法)在工作节点数、覆盖度和是否有盲点等方面进行比较.实验中,假设监测区域是150 m×150 m的矩形区域,节点的感知半径为10 m,传输半径为20 m.

3.1盲 点

衡量区域覆盖算法一个主要的指标是该算法是否产生盲点.由于在文中算法的第2阶段步骤(3)和步骤

(4)使用CCP算法来判断节点是否为冗余节点,当部署节点很多时,CCP算法不产生盲点,所以当部署节点比较多时,文中提出的算法也不会产生盲点.在图4中,比较了不同算法产生的盲点数.随着部署节点的增加,盲点个数越来越少,当部署节点数到达一定个数时,所有算法都不产生盲点.

图4　算法的盲点数比较曲线图

3.2工作节点

由于工作节点数与网络生命期成反相关关系,在满足覆盖的情况下,工作的节点数越少,网络生命期越长,故工作节点数能很好反映网络生命期.在图5中显示了工作节点数与部署节点数的关系,该实验要求的覆盖度为1,可看出,文中算法生成的工作节点数比其他算法的都要少,其中,Ottawa算法产生的工作节点数大概是其他算法的3倍多,而且随着部署节点数的增多,工作节点数不断增多,而其他算法产生的工作节点数保持在一定范围不变.观察文中算法产生的工作节点数可知,随着部署节点不断增多,工作节点数则不断减少.为更精确地比较文中算法与CCP算法生成的工作节点数,表1显示了这两个算法产生的工作节点个数.从表1可知,文中算法产生的工作节点数比CCP算法大概少10%左右,而且随着部署节点个数的增加,文中算法产生的工作节点数不断减少.分析文中算法可知,部署节点越多,在最佳位置的节点越多,生成的工作节点感知区域重叠越少,所以工作节点数就越少.当部署节点无限多时,文中算法产生的节点数则达到图2所示的比较理想的情况.

3.3平均覆盖度

图6比较了各算法的平均覆盖度.显示了在部署节点个数不同情况下各算法的平均覆盖度,部署节点个数从350依次递增到800.除Ottawa算法的平均覆盖度在不断增长外,其他算法的平均覆盖度在2.0左右.还能看到,文中算法的平均覆盖度在不同的部署节点下都比其他算法要低,并且随着部署节点的不断增多,平均覆盖度在不断减小.当部署节点很多时,文中算法要优于其他算法.

表1　工作节点

图5　算法的工作节点数比较曲线图

图6　算法的平均覆盖度比较曲线图

4　结束语

笔者提出了寻找最小工作节点集的覆盖算法,该算法包括两阶段:第1阶段可以运行任一覆盖算法,文中选择CCP算法作为第1阶段运行的算法,在第1阶段运行完以后节点只有两种状态:工作节点状态和假休眠节点状态.在第2阶段对工作节点进行替换,它通过循环迭代使工作节点数不断减少.这样文中算法得到的工作节点数不比第1阶段工作节点数多.由实验可知,文中算法在工作节点数及平均覆盖度方面都要优于其他算法,且随着部署节点的增多,工作节点及平均覆盖度在不断趋近于理想情况.虽然文中算法能得到更少的工作节点数,但是还没有达到最理想情况,特别是在部署节点少的情况下.下一步将对该覆盖算法作进一步的研究,提出一个在部署节点不是很多的情况下能产生更少工作节点数的算法,让更多的节点休眠,最大限度地延长网络生命周期.

[1]ALI R A,HOSSEIN Y M,MASOUD R A.Optimized Congestion Management Protocol for Healthcare Wireless Sensor Networks[J].Wireless Personal Communications,2014,75(1):11-34.

[2]GHASEMIGOL M,GHAEMI-BAFGHI A,YAGHMAEE-MOGHADDAM M H,et al.Anomaly Detection and Foresight Response Strategy for Wireless Sensor Networks[J].Wireless Networks,2015,21(5):1425-1442.

[3]ANJU S,PAL S R.Survey on Coverage Problems in Wireless Sensor Networks[J].Wireless Personal Communications,2015,80(4):1475-1500.

[4]齐小刚,陆赞赞,郑耿忠,等.一种低能耗低时延的睡眠调度算法[J].西安电子科技大学学报,2015,42(1): 124-129. QI Xiaogan,LU Zanzan,ZHENG Gengzhong,et al.Low-power and Low-delay Sheep Scheduling Algorithm Based on the Data Aggregation Tree[J].Journal of Xidian University,2015,42(1):124-129.

[5]KHAN J A,QURESHI H K,IQBAL A.Energy Management in Wireless Sensor Networks:a Survey[J].Computers &Electrical Engineering,2015,41:159-176.

[6]XU Y,HEIDEMANN J,ESTRIN D.Geography-informed Energy Conservation for Ad Hoc Routing[C]//Proceedings of the Annual International Conferece on Mobile Computing and Networking.New York:ACM,2001:70-84.

[7]TIAN D,GEORGANAS N D.A Coverage-preserving Node Scheduling Scheme for Large Wireless Sensor Networks [C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications.New York:ACM,2002:32-41.

[8]BOUKERCHE A,FEI X,ARAUJO R B.An Optimal Coverage-preserving Scheme for Wireless Sensor Networks Based on Local Information Exchange[J].Computer Communications,2007,30(14):2708-2720.

[9]XING G L,WANG X R,ZHANG Y F,et al.Integrated Coverage and Connectivity Configuration for Energy Conservation in Sensor Networks[J].ACM Transactions on Sensor Networks,2005,1(1):36-72.

[10]LIU Y H,PU J H,ZHANG S,et al.A Localized Coverage Preserving Protocol for Wireless Sensor Networks[J]. Sensors,2009,9(1):281-302.

[11]YU J G,DENG X,YU D X,et al.CWSC:Connected k-coverage Working Sets Construction Algorithm in Wireless Sensor Networks[J].AEU-International Journal of Electronics and Communications,2013,67(11):937-946

[12]LIU Y H,SUO L X,SUN D Y,et al.A Virtual Square Grid-based Coverage Algorithm of Redundant Node for Wireless Sensor Network[J].Journal of Network and Computer Applications,2013,36(2):811-817.

(编辑:齐淑娟)

Coverage algorithm for finding the minimum working sets in WSNs

WANG Aimin1,2,LIU Yongqiang1,ZHANG Jing1,LIU Yanheng1,2
(1.College of Computer Science and Technology,Jilin Univ.,Changchun 130012,China;2.Key Lab. of Symbolic Computation and Knowledge Engineering of Ministry of Edu.,Jilin Univ.,Changchun 130012,China)

Since the existing coverage algorithm has a lot of redundant nodes,a coverage algorithm for finding the minimum working sets in WSNs(FMWS)is proposed.The algorithm is divided into two phases:the first phase runs an existing coverage algorithm;the second phase runs an algorithm that uses fewer working nodes to replace more working nodes,with the number of working nodes continuously decreasing through iteration. Simulation shows that the proposed algorithm can obtain more sleep nodes than other algorithms.It can make the number of working nodes reduce around 10%,so as to prolong the network life.

wireless sensor networks;coverage;sleep scheduling;sleep order

TP393

A

1001-2400(2016)04-0141-06

10.3969/j.issn.1001-2400.2016.04.025

2015-04-13 网络出版时间：2015-10-21

国家自然科学基金资助项目(61073164)

王爱民(1970-),男,副教授,博士,E-mail:wangam@jlu.edu.cn.

网络出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.050.html