Connected Coverage Scheduling Algorithm for Heterogeneous Directional Sensor Networks

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

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

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

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

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

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

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

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

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

第二部分种群使用反向学习产生，先随机产生种群中每个染色体的初始值$P = ({p_1},{p_2}, \cdots ,{p_n})$, ${p_i} \in [L,H]$，每个染色体的基因为：

2)非性繁殖过程的改进

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

式中，k为当前的迭代次数；K为最大迭代次数；${\text{PA}}{{\text{R}}_{\max }} = 0.8$；${\text{PA}}{{\text{R}}_{\min }} = 0.8$^[20]。

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

式中，r1，r2，r3，r4，r5为种群中不同于i的个体；$X_{{\text{best}}}^t$为迭代次数为t时种群中适应度最好的个体；$f(X_i^t)$表示个体$X_i^t$的适应度；${f_{{\text{avg}}}}({X^t})$表示迭代次数为t时种群的平均适应度。

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

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

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

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

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

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

1) 解质量的评价

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

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

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

式中，${\gamma _1}$、${\gamma _2}$和${\gamma _3}$为${f_1}$、${f_2}$和${f_3}$对应的系数；${\text{ran}}{{\text{d}}_i}$为区间(0,1)之间的随机数。

2) 解的表示

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

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

按照珊瑚礁算法步骤，对本文提出的ECRO算法进行时间复杂度的理论分析。种群初始化包括解的表示和健康度函数评价两个过程，其时间复杂度为${\text{TC}}1 = O(WL \times {\text{pro}} \times D) + O{(WL \times {\text{pro}})^2}$，D为解的维数也就是染色体的长度，其他参数的含义与前面相同，采用时间复杂度为$O{(WL \times {\text{pro}})^2}$排序算法完成健康度函数评价；新个体产生过程中，非性繁殖过程中直接来自父代和随机产生个体的时间复杂度之和，为${\text{TC}}2 = O((WL \times {\text{pro}} \times {F_a}D)[(1 - {\lambda _i}) \times 1 + {\lambda _i} \times (1 - {c_r} - {1 \mathord{\left/ {\vphantom {1 D}} \right. } D}) \times 1])$，来自父代个体差分变异操作的非性繁殖新个体按照式(8)～式(10)需要得到种群的平均适应度和适应度最好的个体，因此其所需的时间复杂度为${\text{TC}}3 = O(WL \times {\text{pro}} \times {F_a} \times I\_{\text{MAX}} \times {{D}} )^2 \times {\lambda _i} ({c_r} -1/D) $，有性繁殖过程的时间复杂度为${\text{TC}}4 = O((WL \times {\text{pro}} \times (1 - {F_a}) \times I\_{\text{MAX}}) \times D)^2 {\lambda _i}({c_r} + 1/D))$，竞争珊瑚礁过程中，每次迭代需要进行比较操作的数学期望为$\displaystyle\sum\limits_{i = 1}^{T\_{\text{MAX}}} {i \times {1 \mathord{\left/ {\vphantom {1 {T\_{\text{MAX = }}{{(1 + T\_{\text{MAX}})} \mathord{\left/ {\vphantom {{(1 + T\_{\text{MAX}})} 2}} \right. } 2}}}} \right. } {T\_{\text{MAX = }}{{(1 + T\_{\text{MAX}})} \mathord{\left/ {\vphantom {{(1 + T\_{\text{MAX}})} 2}} \right. } 2}}}}$。因此，时间复杂度为${\text{TC}}5 = O(WL \times {\text{pro}} \times I\_{\text{MAX}} (1 + T\_{\text{MAX}}) / 2)$；最差个体提升过程中，需要找到现有种群中健康度最差的个体，其所需的时间复杂度为${\text{TC}}6 = O(WL \times {\text{pro}})$ 。

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

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

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

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

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

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

1) 收敛性能比较

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

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

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

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

设置不同的节点总数，等比例混合3种类型的传感器节点，研究节点数量对网络寿命的影响。监测目标数为8，其他参数值与前面相同。从图5的求解结果可以得出：1)随着部署节点数的增加，网络的寿命也随之延长。究其原因在于，传感器节点数量的增加使得可选的用于工作的感知方向增多，导致满足监测覆盖需求的集合数目随之增加；2)在部署节点数固定的情况下，提出的ECRO算法明显优于其他算法。如当节点数为60时，与贪婪算法Greedy、LADE、未改进的CRO算法和EHS算法^[12]相比，改进算法寿命分别延长97%、27.4% 、33.9%和21.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算法表现最好，验证了改进算法的优越性。

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