无线传感网络中基于DSC的记忆式算法研究*

颜 源,宰文姣

(1.湛江师范学院基础教育学院,广东 湛江 524048;2.四川师范大学工学院,成都 610101)



无线传感网络中基于DSC的记忆式算法研究*

颜 源1*,宰文姣2

(1.湛江师范学院基础教育学院,广东 湛江 524048;2.四川师范大学工学院,成都 610101)

网络寿命是影响无线传感网络WSN(Wireless Sensor Network)应用最关键因素之一,受到广泛关注。将所有传感节点划分为不相交的传感节点覆盖(Sensor covers)子集,致使每个cover能够覆盖所有目标节点,并且所有cover轮流工作,这是延长网络寿命的有效方案。因此,可通过最大化cover数提高网络寿命,即求解不相交覆盖集DSC(Disjoint Set Cover)问题。为此,提出基于IMA(Improved Memetic Algorithm)算法求解DSC问题。IMA算法先建立初始矩阵Initial Population,再经优化Optimizer阶段、改进Improver阶段,形成最大化covers。仿真结果表明,与其他启发式算法和进化算法相比,提出的IMA算法能够形成最大化的covers。

无线传感网络;网络寿命;不相交覆盖集;记忆式算法;上限逼近值

由传感节点组建的无线传感网络WSNs(Wireless Sensor Networks)被广泛应用,如栖息地监控、环境监控[2-3]以及监视系统等[4]。实际上,传感节点是一个微型设备,有4个基础模块组成:从物理环境收集数据的感测模块、数据处理的处理模块、数据存储的记忆模块以及数据传输的无线通信模块。此外,传感节点利用电池作为能量进行工作,但是,电池属于有限能量,并且在WSNs中不能给传感节点切换电池(当电池耗尽时)。在这种情况下,传感节点只能利用有限的能量(电池)进行长期的监测目标的任务。因此,对于所有传感节点而言,优化能量效率是至关重要[5]。WSN实施过程中,能量利用效率被认为是一个重要问题。

合理调度传感节点工作是一个有效的节省能量的策略。传感节点在工作和休眠模式进行合理的切换,致使传感节点以最小能量消耗能够覆盖(cover)所有目标节点。覆盖指的是网络目标至少能被一个传感节点监控,即每个目标至少在一个传感节点监测区域范围内。

在保证所有目标被覆盖的前提条件下,采用有效算法节省传感节点能量,最大化网络寿命被广泛研究。如最大限制最小约束启发式算法混合整数规划MIP(Mixed Integer Programming)[6]、Greedy-MSC启发式算法[7]和基于最大覆盖集问题的启发式算法[8]等。寻找最大覆盖集等价于最大化不相交集合。即在特定时间,在保证能监测目标节点的前提下,仅一个传感节点覆盖区域需要工作,而其他传感节点的覆盖区域进入休眠模式,从而在不影响监测目标节点的情况下,节省传感节点能量。这种模式就是不相交集覆盖DSC(disjoint Set Cover)问题。

目前,有多种方案求解DSC问题,如贪婪Greedy[9]、IGA(Integer Genetic Algorithm)[10]、MA(Memetic Algorithm)[11]等。此外,文献[7]提出利用线性规划和Greedy混合算法求解DSC问题。首先,利用整数规划和非线性限制计算最大覆盖集,然后,再利用线性限制将些问题转化为线性规划。Ding等[6]还证实了DSC问题是NP-complete。

与其他算法相比,文献[10]采用的IGA算法是最好的。然而,IGA算法适用小型网络。IGA算法的劣势在于它需要网络覆盖集上限值才能计算网络覆盖集数。一旦达到上限值后,每个传感节点随机加入覆盖集(Cover Sets)中。如果一个传感节点覆盖了所有目标节点,那它独自形成一个Cover。一些传感节点集不能覆盖所有目标节点,即使联合其他传感节点,也未必能覆盖所有目标节点,不能形成Cover。此外,传感节点是随机性地加入覆盖集,未能以优化Cover数角度有选择性地加入覆盖集。为此,文献[11]提出MA(Memetic Algorithm)算法。MA算法采用了Genetic算法,并使用局部优化算法提高算法性能。文献[12]提出Learning Automat技术解决DSC问题。每个传感节点向邻居节点广播广告数据包,其包含节点位置、覆盖信息。

为此,本文以识别传感节点的覆盖Cover,监控整个目标节点为目的,提出基于MA的改进IMA(Improver MA)算法。与MA算法相比,IMA算法从全局考虑,将所有传感节点划分为子集,子集覆盖cover所有目标节点,然后每个子集轮流工作,实施监控所有目标节点,进而最大化Cover的数量。即采用了基于IMA算法求解DSC问题,通过这种方式,提高传感节点能量效率,延长网络寿命。

1 系统模型及问题描述

设S={S1,S2,…,Sn}为n个传感节点集,在区域内随机分布,监控m个目标节点T={T1,T2,…,Tm}。每个传感节点Si的坐标表示为(xi,yi),且通信范围为R。每个目标节点Tj的坐标表示为(xj,yj)。若(xi,yi)与(xj,yj)满足式(1),则认为传感节点Si覆盖目标节点Tj。

(xi-xj)2+(yi-yj)2≤R2,1≤i≤n,1≤j≤m

(1)

目标节点Tj可能有一个或多个传感节点所覆盖,但是,实际上只要有一个传感节点覆盖就足够。如果所有传感节点同时覆盖同一个目标节点[13],就产生不必要的损耗。为了克服此问题,需利用DSC将所有传感节点划分为子集,子集覆盖所有目标节点,然后每个子集轮流工作,实施监控所有目标节点,通过这种方式,提高传感节点能量效率,延长网络寿命。

设C={c1,c2,…,ck},且ci⊆S,i=1,2,…,k,表示覆盖集。每个coverci包含一些传感节点,由这些传感节点联合覆盖,实现覆盖所有目标节点。|ci|表示ci的传感节点数。

每个传感节点必须位于一个且只有一个cover内,即ci∩cj=φ,i,j=1,2,…,k,且i≠j。

图1 n=6、m=4的无线传感网络及覆盖范围

图1显示了6个传感节点覆盖4个传感节点的示意图。利用式(1),识别每个传感节点的覆盖区域。传感节点S1覆盖了两个目标节点T1、T2,表示为S1={T1,T2},类似地,S2={T3}、S3={T1,T2,T3,T4}、S4={T1}、S5={T4}以及S6={T2,T3,T4}。

定义矩阵A描述传感节点对目标节点的覆盖情况。如果Si覆盖目标节点Tj,相应矩阵元素Aij的值为1,否则为0,如式(2)所示。

(2)

因此,以图1所示的传感网络为例,形成的矩阵A:

式中:行表示传感节点、列表示目标节点。例如,第1行,S1覆盖了两个目标节点T1、T2,因此,T1、T2两列的值为1,其余列为0。

假定目标节点Tj由k个传感节点覆盖,这些节点可以构成k个covers。这k个covers可作为WSN的网络寿命的上限(upper bound)。因此,upper bound ub:

(3)

从矩阵A可知,每列元素和分别为[3 3 3 3]。最小值为3。因此,图1所述的网络结构的上限ub=3。这个数据说明,目标节点最少由3个传感节点数所覆盖,这就意味着该网络最多可以形成3个cover,从而保证每个cover能够覆盖所有目标节点[14]。以图1网络为例,形成的3个cover分别是c1={S3}、c2={S4,S6}以及c3={S1,S2,S5}。每一个cover均覆盖所有目标节点。其中,c1由一个传感节点S3覆盖,c2、c3由多个传感节点联合覆盖所有目标节点。

本文,需要解决的问题就是:针对网络,计算网络的上限,找到可形成cover,保证每个cover能够覆盖所有目标节点。

2 IMA算法

2.1 MA算法

MA算法采用了Lamarckian理论,即子孙后代offspring能够继承它们父辈的知识或特性,并且MA算法采用随机加入Cover,并没有从优化Cover数的角度,有目的性地选择传感节点加入Cover。而提出的IMA算法采用了提高算子Operators、改进算子Improver以及优化算子Optimizer,通过这3个阶段,最大化Cover数,解决DSC问题,提高网络寿命。

如果一个传感节点或多个传感节点联合覆盖所有目标节点,能形成一个cover。依据mating pool,计算每个矩阵中总的cover数。以矩阵A为例,第1行(传感节点S1)覆盖了两个目标节点,因此,其需要与一个或多个传感节点联合,形成一个cover。假定S1随机性地选择传感节点S2联合,可形成c1=[1 1 0 0]∪[0 0 1 0]=[1 1 1 0]。但是,并没有覆盖所有目标节点(目标节点T4未覆盖),需继续联合操作,直到能覆盖所有目标节点。为此,c1继续与传感节点S3联合,即c1=[1 1 1 0]∪[1 1 1 1]便形成一个cover。类似地,第4行(传感节点S4)不能独自形成cover,需联合其他传感节点(传感节点S5、S6)形成cover,即c1=[1 0 0 0]∪[0 0 0 1]∪[0 1 1 1]=[1 1 1 1]。因此,若采用MA方式,矩阵A所形成的cover数等于2。

依据MA方案,只产生了两个cover,而实际上矩阵A对应的传感网络的上限ub=3,即可以形成3个cover。为此,提出MA的改进算法IMA。

2.2 MA的改进算法IMA

提出的IMA算法先产生initial population矩阵,然后,对其进行变换,在initial population矩阵选取最优的行加入到另一个矩阵,从而形成子矩阵。随后进入优化Optimizer阶段、改进Improver阶段,最终形成最大化的cover。接下来,描述IMA的具体过程。

2.2.1 Initial population

IMA先对网络内传感节点数随机排列,并结合式(2)形成Initial population矩阵I。将Initial population矩阵I称为父矩阵,其类似于传感节点覆盖矩阵A,然后再从父矩阵中筛选覆盖了所有目标节点的传感节点所在的行,并从I中移除该行,形成两个矩阵I′和I″。最初,矩阵I′中存储覆盖了所有目标节点的传感节点,称为子矩阵。若矩阵I中不存在覆盖所有目标节点的传感节点,那么就从矩阵I中选择覆盖目标节点数最多的传感节点移到矩阵I′中。I″中存储未能覆盖所有目标节点的传感节点,仍称为父矩阵。

考虑图1所示的WSNs为例,6个传感节点分布于网络区域内,假定6个传感节点的随机排列数为[6 3 1 4 2 5]。基于这个随机数(第6个传感节点在第1行、第3个传感节点在第2行,以此类推),产生的Initial population矩阵I:

从矩阵I可知,有些传感节点独自覆盖所有目标节点,如传感节点S3(矩阵I的第2行)。为此,IMA算法从父矩阵I中先移除覆盖所有目标节点的传感节点所有行,形成两个矩阵I′和I″,如式(4)所示。

(4)

接下来,进一步对矩阵I′和I″进行变换。

①优化Optimizer阶段

获取了矩阵I′和I″后,进入优化Optimizer阶段,目的在于:在矩阵I″中,通过联合一个或多个传感节点,形成一个Cover。首先从矩阵I″中,选择行值最大所对应的传感节点加入I′,通过式(5)计算。

(5)

矩阵I″包含的所有传感节点中没有覆盖所有目标节点。为此,在Optimizer阶段,从矩阵I″中选择一个传感节点,插入矩阵I′中的尾行。

仍以图1所示的WSNs为例,矩阵I″中,第1行的行值最大,即选择S6加入矩阵I″中,插入矩阵I′中,如式(5)所示。随后,进入Improver阶段。

(6)

②改进Improver阶段

Improver阶段的目的在于选择最佳传感节点,使之能够覆盖矩阵I′的尾行未能覆盖的目标节点,加入I′矩阵,形成一个cover。

首先,检测在Optimizer阶段选择插入矩阵I″的传感节点是否包含所有目标节点,没有包含,则需要找到该传感节点未覆盖的目标节点。利用式(7)要找到刚插入I′尾行对应的传感节点S′未覆盖目标节点。

(7)

式中:i表示该传感节点S′在I′所在的行。m表示目标节点总数。传感节点S′未覆盖的目标节点个数等于矩阵b中非零的个数,非零的数的大小表示第几个目标节点未覆盖。

仍以图1所示的WSNs为例,矩阵I′的尾行S6未覆盖目标节点T1。例如,刚在矩阵I′插入S6,其在第2行,即i=2。因此

={-1(0-1),-2(1-1),-3(1-1),-3(1-1)}

={1,0,0,0}

(8)

依式(8)可知,矩阵b中只有一个非零数,则表明只有一个目标节点未被覆盖,并且该非零数等于1,而表明第1个目标节点未被覆盖,即j=1。

找到未覆盖的目标的节点后,需从矩阵I″中寻找一个传感节点,其能覆盖该目标节点Tj。提出的IMA算法采用式(8)寻找符合条件的传感节点:

cbk={lI″lbk},l=1,2,…,m

(9)

式中:bk表示一维矩阵b的第k个元素,m为矩阵I″的行数。

cbk中非零的数h表示矩阵I″中第h行所在的传感节点能够覆盖Tj。

以式(6)为例,可得cb1={1 0 3 0},如式(10)所示。

cb1={1I″112I″213I″314I″41}

={1×1 2×0 3×1 4×0}

={1 0 3 0}

(10)

cb1={1 0 3 0}则表明矩阵I″中第1行、第3行所在的传感节点能够覆盖第1个目标节点T1。

综上所述可知,通过这种方式能够找到矩阵b中未被覆盖的目标节点Tj,并能够从矩阵I″找到能够覆盖Tj的传感节点。

注意式(7),只有一个非零数,意味着只有一个目标节点未被覆盖。若出现多个目标节点未被覆盖时,需要从矩阵I″找到能够覆盖所有未被覆盖的目标节点的传感节点。为此,可利用式(11)找到这类传感节点。

d=∩cbk

(11)

若d=φ,则表明矩阵I″中没有能够覆盖矩阵b中所有未被覆盖的目标节点的传感节点。在这种情况下,退优寻其次,寻找能够覆盖矩阵b中最多未被覆盖的目标节点的传感节点。

仍以上事例为例,矩阵b中只有一个目标节点未,d={1,3}表明第1个传感节点、第3个传感节点能够覆盖该目标节点。

最后,IMA算法需要从d中选择一个覆盖的目标节点数最少的传感节点数:

e=minimum target(d)

(12)

以d={1,3}为例,依据式(12)选择第3个传感节点,即e=3。因为第1个传感节点覆盖了两个目标节点([1 1 0 0]),而第3个传感节点覆盖了只有一个传感节点([1 0 0 0])。

确定了e=3值后,将从I″中选择该传感节点插入矩阵I′,如式(12)所示。

(13)

从式矩阵I′、I″可知,共形成了3个cover,如式(14)所示。每个cover覆盖了所有目标节点。

(14)

若选择第1个传感节点插入,即e=1:

这样的话,可能形成两个cover,如式(15)所示。

(15)

通过这个事例表明提出的IMA算法能够提高cover的个数。

整个IMA算法的步骤如下:

①随机排列传感节点,依据式(2)产生Initial population矩阵I,并将矩阵I中移除覆盖所有目标节点所对就的行,形成I′和I″。

②进入Optimizer阶段:依据式(5),从矩阵I″中移出覆盖目标节点最多的传感节点,并插入矩阵I′尾行,形成新的矩阵I′和I″;

④利用式(9)cbk={lI″lbk},计算I″中能够覆盖目标节点Tj的传感节点所在行。

⑤利用式(11)计算d=∩cbk;

⑥利用式(12)计算e=minimum target(d);

⑦从I″中选择e行插入矩阵I′。最后矩阵I′和I″的传感节点能够形成最大的cover数。

3 仿真及性能分析

考虑网格区域进行仿真,采用MATLAB软件评估IMA算法性能,并与MA[11]、IGA[9]和MCMCC[15]、MC-MIP[6]进行比较。引用Upper bound是cover的最大数。如果算法达到Upper bound,则说明其是最优的算法。因此,作归一化处理,将各算法的cover数除以Upper bound,称为上限逼近值,值越大,说明越接近上限值,性能越好。当等于1时,说明等于上限值,达到最优。每次实验重复进行20次,取平均值作为最终的仿真数据。

①通信范围的影响

图2描述了n=90、m=10网络的内各算法的上限逼近值。从图2可知,3个算法(IMA、IGA、GA)在通信范围R小于300时,上限逼近值为1,达到上限值。当大于300时,上限逼近值开始下降。然而,与IGA、GA、MCMCC算法相比,提出的IMA算法下降很少,从图2的第1个子图可知,最小值为0.99。而GA、MCMCC的最小值达到0.97。

图2 通信范围R对cover数的影响曲线

②目标节点个数m的影响

本次仿真考查目标节点个数m对cover数的影响,并两类场景:90个传感节点的网络(n=90)、300个传感节点的网络(n=300)。

图3描述了n=90、通信范围R=200的无线传感网络的cover数随目标节点个数m的变化情况,其中目标节点数m从10、20、30、40、50、75、100、150、200、250和300变化。从图3可知,MA和IGA算法在90个传感节点的小型网络环境下最优,上限逼近值均等于1,提出的IMA算法的上限逼近值在0.9982附近。其中,MCMCC算法方案最差,上限逼近值在0.975 3附近。

图3 目标节点个数m对cover数的影响曲线

图4描绘n=300、通信范围R=200时无线传感网络的cover数随目标节点个数m的变化情况,其中目标节点数m从10、20、30、40、50、75、100、150、200、250和300变化。从图4可知,提出的IMA算法最优,而MA和IGA算法性能开始下降,这些数据表明MA、IGA算法只适合小型传感网络,而IMA适合较大型网络。

图4 目标节点个数m对cover数的影响曲线

③传感节点个数n的影响

图5描述了传感节点个数n对m=10、通信范围为200的网络环境的cover数的影响曲线。如图5可知,提出的IMA算法最优,除了个别值不等1之外,其余均等于1。而MA、IGA和MCMCC均随着传感节点数增加,上限逼近值下降,MCMCC算法下降最快,低至0.965。

此外,为了更充分地分析IMA算法在形成cover数优势,在n=90、通信范围R=200的无线传感网络环境,测试IMA、IGA、MC-MIP以及MCMCC在20次的重复仿真中cover数的最大数、平均数,结果如图6、图7所示。

从图6和图7可知,提出的IMA算法的cover的最大数与IGA相近,并远远优于MC-MIP和MCMCC,并且IMA算法的cover的平均数最大,比MCMCC算法提高了近4个。

图5 传感节点个数n对cover数的影响曲线

图6 cover的最大数(n=90、R=200)

图7 cover的平均数(n=90、R=200)

通过上述仿真数据可知,提出的IMA算法能够有效解决DSC问题,并使得网络内的cover数达到最大,逼近上限值,从而有效提高传感节点的能量利用率,提高网络寿命。

4 总结

本文采用IMA算法求解DSC问题,进而延长WSN的网络寿命。IMA算法先依据WSN的拓扑结构建立初始矩阵Initial populationI,随后从I筛选能够覆盖所有目标节点的传感节点,形成矩阵I′和I″,再经优化Optimizer阶段、改进Improver阶段,形成最大化covers,每个cover覆盖所有目标节点。每个cover轮流工作,节省传感节点能量,最终,实现延长网络寿命的目的。仿真结果表明,与启发式算法相比,提出的IMA算法能够逼近cover上限。

[1]Fatme M,Eric T,Guoliang X. Maximizing Network Topology Lifetime Mobile Node Rotation[J]. IEEE Transactions on Parallel and Distributed Systems. 2013,34(5):1-14.

[2]Zitterbart D,Wienecke B,Butler J,et al. Coordinated Movements Prevent Jamming in an Emperor Penguin Huddle. PLoS One,2011,6(6):202-216.

[3]Xu H,Huang L,Zhang Y,et al. Energy-Efficient Cooperative Data Aggregation for Wireless Sensor Networks[J]. J Parallel Distrib Comput,2010,70(9):953-961.

[4]El-Moukaddem F,Torng E,Xing G. Maximizing Data Gathering Capacity of Wireless Sensor Networks Using Mobile Relays[C]//IEEE MASS,2010:312-321.

[5]夏韵,陈志刚,曾锋. 无线传感器网络中基于MDS-MCC问题的启发式算法研究[J]. 计算机工程与科学,2013,35(4):53-58.

[6]Mihaela Cardei,Ding-Zhu Du. Improving Wireless Sensor Network Lifetime through Power Aware Organization[J]. Wireless Networks,2005,1(3):333-340.

[7]Mihaela Cardei,Thai M T,Yingshu Li,et al. Energy Efficient Target Coverage in Wireless Sensor Networks[J]. IEEE INFOCOM,2005:1976-1984.

[8]Mihaela Carde. Energy Efficient Coverage Problems in Wireless Ad-Hoc Sensor Networks[J]. Computer Communications,2006,29(4):413-420.

[9]Zoe Abrams,Ashish Goel,Serge Plotkin. Setk-Cover Algorithms for Energy Efficient Monitoring in Wireless Sensor Networks. IPSN’04,2004:424-432.

[10]Chih-Chung Lai,Chuan-Kang Ting,Ren-Song Ko. An Effective Genetic Algorithm to Improve Wireless Sensor Network Lifetime for Large-Scale Surveillance Applications[C]//proceedings of the 2007 Congress on Evolutionary Computation. 2007:3531-3538.

[11]Chuan-Kang Ting,Chien-Chih Liao. A Memetic Algorithm for Extending Wireless Sensor Network Lifetime[J]. Information Sciences,2010,180(24):4818-4833.

[12]Mostafaei H,Meybodi M R. Maximizing Lifetime of Target Coverage in Wireless Sensor Networks Using Learning Automata[J]. Wireless Personal Communications,2013,71(2):1461-1477.

[13]王铨,黄战华,蔡怀宇,等. 高精度分划自动对焦评价函数研究[J]. 传感技术学报,2013,26(1):49-53.

[14]吴晓平,谈士力. 基于半定规划的无线传感网络定位算法的性能分析[J]. 传感技术学,2012,25(12):1731-1738.

[15]Sasa Slijepcevic,Miodrag Potkonjak. Power Efficient Organization of Wireless Sensor Metworks[J]. IEEE International Conference on Wireless Communications,2001:472-476.

Research of Memetic Algorithm Based on DSC Problem in Wireless Sensor Networks*

YANYuan1*,ZAIWenjiao2

(1.College of Foundation Studies,Zhanjiang Normal University,Zhanjiang Guangdong 524048,China;2.Institute of Engineer,Sichuan Normal University,Chengdu 610101,China)

A critical aspect of applications in wireless sensor network(WSN)is its lifetime. This issue has received increased attention due to the recent advances in affordable and efficient integrated electronic devices. One approach to extend the wireless sensor network lifetime is to divide the deployed set of all sensors into disjoint subsets of sensor covers,such that each sensor cover can cover all targets and get activated one after another. The sensor network lifetime can be increased by identifying the maximum number of covers and it can be identified through disjoint set cover(DSC). In this paper,a novel improved memetic algorithm(IMA)is proposed to give a better solution to the DSC. In IMA algorithm,firstly establish the initial population,then optimize process,improve process,finally maximize the numbers of covers. Simulation results show that the proposed IMA can maximize the total number of covers compared with several heuristic and evolutionary algorithm.

wireless sensor networks;network lifetime;disjoint set cover;memetic algorithm;upper bound

颜 源(1980-),女,四川西昌人,硕士,讲师,主要研究方向为WSN同步技术与应用、物联网视频感知与识别技;

宰文姣(1979-),女,湖北武汉人,工学硕士,副教授,研究方向为智能控制、电机调速等。

项目来源:四川省教育厅自然科学基金项目(13ZB0163);国家自然科学基金项目(61373162);国家科技计划支撑项目(2012BAH76F01)

2014-10-24 修改日期:2014-12-14

C:7110

10.3969/j.issn.1004-1699.2015.03.023

TPT393

A

1004-1699(2015)03-0430-07