异构有向传感器网络连通覆盖调度算法

李 明，胡江平，曹晓莉

(1. 电子科技大学自动化工程学院 成都 611731；2. 重庆工商大学人工智能学院 重庆 南岸区 400067)

近年来，无线视频传感器(其感知具有方向性，隶属于有向传感器)逐渐取代有线视频监控传感器，其安装简便，价格便宜，应用场景不断拓展。传感器网络节点覆盖调度对于网络同步与分布式优化起着重要作用[1-4]。在满足监测目标监测覆盖的要求下，如何借助节点调度算法延长有向传感器网络的工作时间是有向传感器网络的重要研究内容。文献[5]提出一种基于概率覆盖圆的连通有向传感器网络的目标覆盖增强算法。文献[6]提出了一种面向有向传感器网络的基于遗传算法的k覆盖算法，通过求解多个满足目标k覆盖要求且节点数量最少的集合延长网络的寿命。文献[7]通过建立一种混合二进制整数线性规划模型，求解得到多个互不相交的覆盖集合来延长有向传感器网络的寿命。这些研究都是假设参与节点调度的传感器节点参数相同，未考虑异构节点对调度算法的影响。同时，均假定监测目标在区域内均匀分布，未考虑监测目标的重要性、出现频率对网络服务质量的影响。对于异构有向传感器网络，文献[8]提出两种启发式算法解决有向传感器网络的寿命最大化问题，两种算法的区别在于每次选取节点感知方向的标准不同。一种为每次选取对目标覆盖贡献最大(也就是覆盖最多目标)的感知方向，另一种为每次选择能覆盖监测目标且能量最少的感知方向，两种算法结束的条件均为直到所有的目标满足覆盖要求。文献[9]提出一种基于学习自动机的算法解决感知半径可调的有向传感器网络的k-覆盖问题。文献[10]提出一种基于遗传算法的寿命最大化策略来延长半径可调的有向传感器网络的寿命。针对异构有向传感器网络的寿命优化问题，利用集合覆盖的思想，文献[11]通过改进的和声搜索算法求解满足目标覆盖要求的集合，解决差异化覆盖条件下异构有向传感网络寿命的问题。文献[12]将学习自动机引入差分进化算法，实现算法参数的自适应并增强算法的优化能力，使寿命达到最大化。但这些文献没有考虑网络的连通性，使得算法在工程实践中受到影响。尽管文献[13-14]对差异化覆盖连通问题进行了研究，但其研究对象为全向感知和节点同构的传感器网络，研究成果不适用于感知模型为有向的异构有向传感器网络。

针对上述研究中存在的问题，在满足应用场景监测目标覆盖要求差异化和网络连通的条件下，本文提出一种面向异构有向传感器网络的节点调度算法，达到降低网络能耗和延长网络工作时长的目标。

1 问题描述及数学建模

在二维监测区域中随机部署N个不同的感知半径ri、通信半径ci、携带能量Ei、感知角度 θi的传感器节点si(i=1,2,···,N)，用于监测W个目标。由节点的感知角度得出可用的感知方向为，本文假定节点的感知方向不重叠，在工作状态时传感器节点消耗的能量ei不同，非工作状态时节点不消耗能量，则可得出节点的寿命为Li=Ei/ei。根据监测目标出现的频率将其分为重点目标(出现频率高)和非重点目标。为保证网络服务质量和网络可靠性，要求至少两个传感器节点对对重点目标进行监测，其他目标只要能监测到就符合应用需求。

定义传感网络的寿命[12]网络中的传感器节点能提供符合监测目标的监测要求且能保持网络连通的时间。

在满足监测目标的监测覆盖需求和保持网络连通的前提下，如何延长传感网络的寿命是本文要解决的问题。其形式化的描述为：

除了增加式(5)的连通要求，该数学模型与文献[11]相同。式中，K表示满足覆盖连通要求的集合数；tk为第k个覆盖连通集的工作时长，其大小由集合中能量最小的节点决定；Di,j为 节点si的第j个感知方向；Ck为第k个符合连通覆盖要求的节点集合；C_Tk,m表 示在Ck中能覆盖监测目标Tm的感知方向的集合； Req(Tm)表 示监测目标Tm要求同时被多少个传感器节点监测，取值为正整数，由目标本身的特性或出现的区域决定。采用文献[15]中的有边界的帕累托分布模拟目标在某一时间段内的出现情况，其参数取值与文献[15]相同，仿真结果如图1 所示。其中，“□”目标出现频繁的区域为重点区域，对于这些区域的监测目标要求Req(Tm)≥2， 其他区域 Req(Tm)=1即可。式(2)对节点的能量进行约束，使得其工作时消耗的总能量不超过其携带的总能量。式(3)表示传感器节点在工作状态时只能有一个感知方向。式(4)表示由传感器节点构成的集合能满足所有监测目标要求。式(5)保证传感器节点之间是相互连通的，本文假定传感器节点在其通信半径内有其他节点存在时则该节点连通的。

图1 监测目标出现区域示意图

考虑到集合覆盖问题为NP-hard 问题[11]，本文利用珊瑚礁算法进行求解。

2 连通覆盖调度算法

2.1 原始珊瑚礁优化算法

珊瑚礁算法[16]是一种模拟珊瑚虫行为的智能进化算法，已用于求解农场风力资源优化、有向传感器网络资源优化[17]等组合优化问题。该算法的步骤为：初始化、繁殖过程、竞争过程和淘汰过程。其中，种群初始化实现算法参数的初始化，包括：珊瑚礁的面积(通常为W×L矩形)、珊瑚礁中存在珊瑚虫的比例pro、迭代数I_MAX、非性繁殖(即雌雄同体)的比重Fa、迭代过程中子代寻找珊瑚礁附着时允许尝试的最大次数T_MAX、珊瑚虫被淘汰的概率pro_coral 和被淘汰珊瑚虫与珊瑚虫总数的比重pro_no。珊瑚虫的繁殖行为包括：非性繁殖行为(其比例占所有繁殖行为的比例为Fa)和在符合要求范围内随机产生子代和有性繁殖行为(其比例占所有繁殖行为的比例为Fb)。珊瑚虫竞争珊瑚礁的过程，也就是珊瑚虫寻找可附着珊瑚礁的过程。若该珊瑚礁上没有其他珊瑚虫，则珊瑚虫直接可占据此珊瑚礁；否则，需要进行珊瑚虫适应度大小的比较，根据比较结果择优附着在珊瑚礁上。若竞争失败，可尝试占据其他珊瑚礁，若达到最大尝试次数仍未找到可附着的珊瑚礁，则该珊瑚虫死亡。在淘汰过程中，依据适应度排序，对珊瑚虫进行淘汰操作。淘汰后的珊瑚虫其附着的珊瑚礁随之被空出，以备后续珊瑚虫使用。

2.2 增强的珊瑚礁算法

1) 种群初始化策略的改进

种群初始化后产生的初始解对算法的优化能力具有非常重要的影响。为了使初始解均匀分布，将种群数均匀分为两部分，每一部分采用不同的初始化策略。第一部分种群使用低差异的SOBOL 序列产生，使得初始解更均匀的分布在多维超体中[18]。其数学表达式为：

式中，变量L和H分别表示解允许取值范围的最小值和最大值；S为SOBOL 序列产生的[0,1]的随机数。

第二部分种群使用反向学习产生，先随机产生种群中每个染色体的初始值P=(p1,p2,···,pn),pi∈[L,H]，每个染色体的基因为：

2)非性繁殖过程的改进

CRO 算法中的非性繁殖过程是随机产生的，这种操作不利于继承种群中的较优解。为保存非性繁殖过程中的优秀解，借鉴生物地理学算法[19]、和声搜索算法[20]和差分进化算法[12]对其进行改进。具体为，子代个体中每一维的来源有3 种可能：① 直接来自父代的概率为1 −λi，为避免继承较差的基因，以概率PAR[20]对其进行随机扰动；② 在可行区域内随机产生，其概率为 λi(1−cr−1/D)，cr为差分进化算法中的交叉概率，本文取0.9[12]。③ 剩余的 λi(cr+1/D)的概率来自非性繁殖父代个体之间的差分变异操作。变量 λi为生物地理学算法的参数，为解的第i维迁移率[19]，λi=i/D，参数D是解的维数；PAR 为来自和声搜索算法的参数，采用文献[20]自适应缩放因子，即：

式中，k为当前的迭代次数；K为最大迭代次数；PARmax=0.8； PARmin=0.8[20]。

差分变异操作中差分变异策略和控制参数对算法的性能有重要影响。为增强算法性能，采用自适应变异策略和设置控制参数，变异策略为：

式中，r1，r2，r3，r4，r5 为种群中不同于i的个体；为迭代次数为t时种群中适应度最好的个体；表 示个体的适应度；favg(Xt)表示迭代次数为t时种群的平均适应度。

采用自适应的参数选择策略，具体为：

式中，Fmin和Fmax分别表示F的最小值和最大值。当种群个体有早熟的趋势时，采用较大的F值进行抑制，保持种群的多样性；反之，当种群个体收敛较慢时，采用较小的F值加快种群的收敛；其他情况下，产生随机的F。

3)混合策略提升种群中的最差个体

在竞争和淘汰过程之间增加最差个体提升过程，通过两种方法改善其优化能力，并通过适应度评价选择两种方法中改善效果最显著的作为其最终的结果。如式(8)的反向学习操作和式(9)的差分操作：

式中，变量L和H分别表示解的最小值和最大值；函数rand()为产生0～1 的随机数；和分别为循环次数为t时种群中适应度最差和最好的个体；F为差分参数，在区间[0.1, 0.9]随机取值。通过适应度评价，选择式(8)和式(9)中表现较好的作为最差个体新的解，可使其跳出其目前所处最差区域，增强其优化能力。

2.3 寿命最大化问题的求解

通过求解尽可能多满足覆盖连通要求的集合，达到延长网络寿命的目的。每次循环完毕后，珊瑚礁算法输出种群中的最优解，执行节点能量的更新，反复迭代，直到满足算法终止的条件。其中要解决解质量的评价和如何表示解这两个关键问题。

1) 解质量的评价

对于珊瑚礁算法而言，解质量的评价也就是设计健康度函数。针对解决问题的特点，设计了3 个优化目标：① 形成尽可能多的满足监测要求的集合；② 形成满足要求的集合后，节点的剩余能量最多；③ 最后一个是要求集合中节点的连通度越高越好。用形式化的语言描述为：

式中，W′表示符合监测覆盖要求的监测目标数量；W表示监测目标的数量；f1的值域为[0,1]；f2是用双曲正切函数表示的剩余能量的函数，取值范围为[0,1]；β 是权重系数，在文中设为1；f3值域为[0,1]。

利用随机线性加权的方法[21]将多目标优化问题变成单目标优化问题，即：

式中， γ1、 γ2和 γ3为f1、f2和f3对 应的系数； r andi为区间(0,1)之间的随机数。

2) 解的表示

考虑到求解问题的特点，对节点和感知方向进行整数编号，根据该编号能确定属于节点的感知方向，如图2 所示。

图2 解的示意图

图中解的每个位置ti的含义如式(11)所述，其中 |Di|为 有向传感器节点si感知方向的数量。由于节点冗余性和特定节点的某个感知方向可覆盖多个监测目标，可能出现解的某个位置的值为0 的情况。

2.4 ECRO 算法时间复杂度分析

结合上述分析，ECRO 算法的总的时间复杂度是上述所有过程时间复杂度的总和，即TC= TC1+TC2+ TC3+ TC4+ TC5+ TC6

3 实验与分析

本节首先测试增强珊瑚礁算法ECRO在数值计算上的性能，然后将其用于解决异构有向传感器网络寿命最大化的问题。

3.1 数值运算

在表1 的4 个测试函数上测试各算法的性能。将遗传算法(genetic algorithm, GA)、模拟退火算法(simulating algorithm, SA)、原始差分进化算法(differential evolution, DE)、文献[11]中的改进和声搜索算法(enhanced harmony search, EHS)和文献[12]中的基于学习自动机的差分进化算法(learning automata differential evolution, LADE)作 为对比算法参与数值运算。函数的具体信息详见表1 所示。

表1 测试函数具体信息

CRO 算法中W×L设为10×5，其他参数Fb、Fa、pro、T_MAX、pro_coral 和pro_no 分别设为0.9,0.1,0.7,3,0.1 和 0.01[16]； ECRO 算 法 中Fmin=0.1，Fmax=0.9[22]，维数n为30，其他参数的值与文献[12]取值相同。算法结果为程序运行30 次所得结果的平均值。从表2 的求解结果可以得出：在F3 函数中，所有参与测试的算法均取得全局优化解0；除此之外的数值测试结果显示，相比较于其他算法，ECRO 算法求解结果最优。数值计算结果表明，与其他算法比较，本文提出的ECRO 算法性能最佳，证明了算法的有效性。

表2 结果比较

3.2 覆盖调度算法性能比较

3.2.1 仿真环境配置

覆盖调度算法的仿真平台为MATLAB 2013。监测区域大小为50 m×50 m，节点数量N为30，每个连通覆盖集合工作时间wt=1s，节点可选的感知方向为 |Di|=，且感知方向之间无重叠区域，其中 θi表 示感知角度 θi。节点信息如表3 所示。监测目标随机分布在监测区域内，其数量W=6。若某一监测目标在某个监测周期里出现频率较高，则认定为重点监测目标，此类监测目标要求被两个传感器节点监测到，其余监测目标被1 个传感器节点监测到即可，每种类型的监测目标数量随机产生。

表3 节点参数表

为更好地衡量改进算法ECRO 的性能，本文提出一种贪婪算法(以下简称Greedy)作为对照算法。其求解步骤为，每一轮选择的感知方向，为以下3 个指标乘积的最大值：1)该感知方向所在节点的剩余能量；2)该感知方向监测目标数量；3)该感知方向与其他已选择节点的连通性(式(5)不等号左端的值)。选择感知方向的操作会一直进行，直到所有监测目标的监测要求被满足，这样就产生了一个符合监测目标要求且连通的感知方向集合。执行节点能量更新操作后，继续下一轮集合的选择，直到不满足覆盖连通要求或节点因能量耗尽而死亡。

3.2.2 结果分析

1) 收敛性能比较

将种群的平均适应度作为种群收敛性能的指标，进行算法收敛性能的比较，图3 为ECRO 和CRO 算法的平均适应度变化情况。观察图3 可以得出，ECRO 和CRO 两种算法都随着迭代次数变大而趋于收敛，并且ECRO 算法种群的平均适应度大于CRO 算法，验证了改进算法ECRO 的收敛性能较好。同时，两种算法在未进入迭代(迭代次数为0)时，ECRO 算法的种群平均适应度优于CRO 算法，证明了本文提出的种群初始化策略的有效性。

图3 算法平均适应度比较

2) 监测要求与网络寿命的关系

假定监测目标数目W=8，用M′代表重点监测目标的数量，其值分别设为3 和5；k′代表重点监测目标对应的监测覆盖要求，其值分别设为2 和3，用ECRO 算法求解覆盖连通问题。从图4 求解得到的结果可以看出：1)节点数越多，网络寿命越长。2)节点数和监测覆盖要求k′固定时，重点目标数M′越大，相应地网络寿命也就越短。3)节点数和重点目标数M′固定时，重点目标的监测覆盖要求k′越大，网络寿命就越短。

图4 不同覆盖要求对节点寿命的影响

3) 均匀比例下节点数量对网络寿命的影响

设置不同的节点总数，等比例混合3 种类型的传感器节点，研究节点数量对网络寿命的影响。监测目标数为8，其他参数值与前面相同。从图5的求解结果可以得出：1)随着部署节点数的增加，网络的寿命也随之延长。究其原因在于，传感器节点数量的增加使得可选的用于工作的感知方向增多，导致满足监测覆盖需求的集合数目随之增加；2)在部署节点数固定的情况下，提出的ECRO 算法明显优于其他算法。如当节点数为60 时，与贪婪算法Greedy、LADE、未改进的CRO 算法和EHS 算法[12]相比，改进算法寿命分别延长97%、27.4% 、33.9%和21.5%。究其原因在于，贪婪算法尽管每一步都是当前最优，但局部最优不保证最终得到全局最优解。改进算法得益于种群初始化、算法过程和最差个体的改进，使得算法优化能力得以增强。

图5 算法比较

4) 非均匀比例下节点数量对网络寿命的影响

研究非均匀比例对网络寿命的影响。表4 为具体构成比例，其中情况1 表示，3 种类型的传感器节点数量都相同，也就是所占的比例均为1/3，情况2 表示3 种传感器节点数量不同，3 种类型节点的参数详见表3。监测目标数设为8，其他的算法参数与前面相同。从图6 的结果可以得出：1)对于某一算法，在部署节点数固定的条件下，与情况1 相比，情况2 中的网络寿命较好。如对于ECRO算法来说，当节点总数为90 时，情形1 的网络寿命为100 s，情形2 网络寿命为120 s，寿命提高20%。2) 在节点比例和部署节点数都相同的条件下，较之其他算法，本文提出的ECRO 算法表现最好，验证了改进算法的优越性。

表4 节点构成比例表

图6 不同节点构成比例下网络寿命的比较

4 结 束 语

本文提出了一种基于增强珊瑚礁算法的网络寿命最大化策略，解决应用场景中监测目标差异化的监测要求和网络连通条件下异构有向传感器节点调度的问题。相比现有的节点调度算法，本文研究问题的特色在于，节点异构、监测目标差异化监测和网络连通的要求更加符合有向传感器网络部署的实际情况。未来将应用本文提出的方法研究三维空间内的异构有向传感器网络节点的覆盖连通调度问题；另外在网络连通方面，将引入中继节点实现网络多跳连通，在此基础上研究更宽泛意义上的异构有向传感器网络连通覆盖调度算法，使得算法更具实用性。